Limbo
|
#include <ChromaticNumber.h>
Classes | |
class | mis_visitor_type |
Public Types | |
typedef GraphType | graph_type |
typedef boost::subgraph < graph_type > | subgraph_type |
typedef boost::graph_traits < graph_type > ::vertex_descriptor | graph_vertex_type |
Public Member Functions | |
int | operator() (subgraph_type g) const |
Protected Member Functions | |
int | chromatic_number (subgraph_type &g) const |
Implement the algorithm in "A note on the complexity of the chromatic number problem", E.L. Lawler Inf. Process. Lett.
Candidates for possible improvments
GraphType | graph type |
Definition at line 52 of file ChromaticNumber.h.
|
inlineprotected |
The chromatic number of G is related to the complement graph of G \ I, where I is maximum independent set. Traversing over all maximum independent sets are necessary to calculate the chromatic number. This function is implemented in a recursive way
g | graph |
Definition at line 110 of file ChromaticNumber.h.
|
inline |
API for computing chromatic number
g | graph |
Definition at line 98 of file ChromaticNumber.h.