limbo::algorithms::coloring::LawlerChromaticNumber< GraphType > Class Template Reference

#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

Detailed Description

template<typename GraphType>
class limbo::algorithms::coloring::LawlerChromaticNumber< GraphType >

Implement the algorithm in "A note on the complexity of the chromatic number problem", E.L. Lawler Inf. Process. Lett.

Candidates for possible improvments

• "Chromatic Number in Time O(2.4023^n) Using Maximal Independent Sets", Jesper Makholm Byskov, BRICS, 2002
• "Small Maximal Independent Sets and Faster Exact Graphing Coloring", David Eppstein, Worksh. Algorithms and Data Structures, 2001

Template Parameters

GraphType

graph type

Definition at line 52 of file ChromaticNumber.h.

Member Function Documentation

template<typename GraphType>

int limbo::algorithms::coloring::LawlerChromaticNumber< GraphType >::chromatic_number ( subgraph_type &  g ) const

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

Parameters

g

graph

Returns

chromatic number of the graph

Definition at line 110 of file ChromaticNumber.h.

template<typename GraphType>

int limbo::algorithms::coloring::LawlerChromaticNumber< GraphType >::operator() ( subgraph_type  g ) const

inline

API for computing chromatic number

Parameters

g

graph

Returns

chromatic number

Definition at line 98 of file ChromaticNumber.h.

---

The documentation for this class was generated from the following file:

• /Users/yibolin/Documents/Projects/Limbo/limbo/algorithms/coloring/ChromaticNumber.h