Opened 10 years ago
Last modified 10 years ago
#5669 closed enhancement
[with patch, needs work] New algorithm for Max Clique in Graph class — at Version 1
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.1 |
Component: | graph theory | Keywords: | independant set stable clique |
Cc: | rlm | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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
Change History (2)
Changed 10 years ago by
comment:1 Changed 10 years ago by
- Description modified (diff)
- Summary changed from [with patch, needs review] New algorithm for Max Clique in Graph class to [with patch, needs work] New algorithm for Max Clique in Graph class
Note: See
TracTickets for help on using
tickets.
Hi,
a couple remarks:
There is more, but the above should keep you busy for a while :)
Cheers,
Michael