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 Typedef Documentation

graph_type

template<typename GraphType>

typedef GraphType limbo::algorithms::coloring::LawlerChromaticNumber< GraphType >::graph_type

Definition at line 56 of file ChromaticNumber.h.

graph_vertex_type

template<typename GraphType>

typedef boost::graph_traits<graph_type>::vertex_descriptor limbo::algorithms::coloring::LawlerChromaticNumber< GraphType >::graph_vertex_type

Definition at line 58 of file ChromaticNumber.h.

subgraph_type

template<typename GraphType>

typedef boost::subgraph<graph_type> limbo::algorithms::coloring::LawlerChromaticNumber< GraphType >::subgraph_type

Definition at line 57 of file ChromaticNumber.h.

Member Function Documentation

chromatic_number()

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.

operator()()

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:

• /home/abuild/rpmbuild/BUILD/limbo-3.5.4-build/limbo-3.5.4/limbo/algorithms/coloring/ChromaticNumber.h