Opened 10 years ago

Last modified 10 years ago

#5669 closed enhancement

[with patch, needs review] New algorithm for Max Clique in Graph class — at Initial Version

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

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

Change History (1)

Changed 10 years ago by ncohen

Note: See TracTickets for help on using tickets.