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

**Note:**See TracTickets for help on using tickets.