id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
5669,New algorithm for Max Clique in Graph class,ncohen,rlm,"I recently had to compute a maximum stable set in a graph with 100 vertices and ended up waiting a whole day ( to no good end ) for Sage to compute it. The current algorithm uses the library NetworkX whose algorithm is not nearly as efficient as Cliquer :
http://www.tkk.fi/~pat/cliquer.html
It is based on an algorithm published in 2002, and it gave me a result in less than a millisecond ;-)
Here are the modification I made :
- I created a spkg file containing the sources of this software for it to be available in SAGE
- I wrote the interface to use it
- I modified the Graph class to use this software instead.
- Added to the function to compute the maximum clique, I added the function Maximum independant set ( which is a similar notion for the complement of a graph, a bit more customary ). As the algorithm provided a function to compute all the maximum cliques, I also added this function
Note: The spkg can be found in http://sage.math.washington.edu/home/mabshoff/SPKG/cliquer-1.2.spkg",enhancement,closed,minor,sage-4.1,graph theory,duplicate,independant set stable clique,rlm,,,,,,,,,