tags:

views:

113

answers:

2
+5  Q: 

Finding max clique in perfect graphs

A fast algorithm to find the size of the largest clique in a perfect graph(this one having odd cycles with at least 1 chord) with about 100 vertices ??

And is there any simpler method than brute force as this is a perfect graph and there should be a polynomial time solution to it. But I am not able to find the algorithm.

Does greedy coloring give optimal coloring in all perfect graphs??

+1  A: 

See page 296, with some work you should write the right linear programming constraint to solve this problem.

http://www.scribd.com/doc/5710463/Geometric-Algorithms-And-Combinatorial-Optimization

yogsototh  2010-06-11 05:51:04
+1: Only answer which addresses perfect graphs, for which the clique problem is in P.
Moron  2010-06-11 12:22:13
A: 

100 vertices? Pffft. Brute force it in a few seconds (perhaps fraction of a second) with Cliquer. http://users.tkk.fi/pat/cliquer.html

Chad Brewbaker  2010-06-11 06:50:49
Can u explain the algorithm(I have seen the documentation) but in simpler terms
copperhead  2010-06-11 06:56:05
Sure. First Cliquer defines a permutation of the vertices. I think by default it is in whatever order you used in the input. Secondly, cliquer iterates finding the largest clique in the set [i....n], from i = n-1 to i=1. Along the way it remembers the largest clique it has found so far and when testing for new cliques it prunes the search when it becomes apparent that from the previously calculated clique sizes it will be impossible for that path of the search to yield a larger clique.
Chad Brewbaker  2010-06-14 07:23:53

related questions

How do I find the Excel column name that corresponds to a given integer?
Calculating a cutting list with the least amount of off cut waste.
Red-Black Trees
How to maintain a recursive invariant in a MySQL database?
RFC calculation in Java need help with algorithm
Best word wrap algorithm?
How do you separate game logic from display?
Most effective way for float and double comparison
Choosing a multiplier for a (string) hash function
Optimizing a search algorithm in C
Find the best combination from a given set of multiple sets
What "already invented" algorithm did you invent?
Designing a Calendar system like Google Calendar
How to overload std::swap()
Looking for algorithm that reverses the sprintf() function output
Merge Sort a Linked List
Puzzle: Find largest rectangle (maximal rectangle problem)
graph serialization
Peak detection of measured signal
Big O, how do you calculate/approximate it?
What problems can be solved, or tackled more easily, using graphs and trees?
Followup: "Sorting" colors by distinctiveness
Efficiently get sorted sums of a sorted list
Function for creating color wheels
Fastest way to get value of pi