?

Log in

No account? Create an account

Whee, cliques! - Journal of Omnifarious

Jun. 29th, 2004

09:39 am - Whee, cliques!

Previous Entry Share Next Entry

This seemed rather interesting.

I am a member of 3 cliques of size 5

Find the largest clique containing:
(Enter your livejournal username here).

Current Mood: [mood icon] curious

Comments:

[User Picture]
From:morning_stand
Date:June 29th, 2004 10:24 am (UTC)
(Link)
*Giggles* You used an exclamation point!!!! <-- I used four.

Yay for interjections :)
(Reply) (Thread)
[User Picture]
From:omnifarious
Date:June 29th, 2004 12:58 pm (UTC)
(Link)

*chuckle*

(Reply) (Parent) (Thread)
[User Picture]
From:eqe
Date:June 29th, 2004 12:49 pm (UTC)
(Link)
That program finds I am in 10 cliques of size 15. The programming discussion behind this problem is also interesting; it's NP-Hard and so is mostly solved with heuristics. I think I'll try the comprehensive solution later.
(Reply) (Thread)
[User Picture]
From:omnifarious
Date:June 29th, 2004 12:57 pm (UTC)
(Link)

From what I know, the problem of finding cliques in a general graph is NP-Complete, but the problem of finding cliques centered around a particular node is O(<number of nodes the node is connected directly to> * <number of edges all those nodes have>) or somewhere thereabouts. I might be wrong though. This is an area I don't know a whole lot about.

(Reply) (Parent) (Thread)
[User Picture]
From:eqe
Date:June 29th, 2004 01:10 pm (UTC)
(Link)
Hmm, I'll have to go doodle some and re-browse my graph theory books. I think you might be right that having a fixed point makes the problem easier.

BTW, I misremembered -- 15 cliques of size 10, not the other way around. The annoying thing is, they're all the same clique with one or two members permuted.
(Reply) (Parent) (Thread)