agape.algos

Class Coloring<V,E>

java.lang.Object

agape.algos.Algorithms<V,E>

agape.algos.Coloring<V,E>

Type Parameters:

V - Vertices type

E - Edges type

public class Coloring<V,E>
extends Algorithms<V,E>

The goal of this class is to compute the minimum number of colors to properly color an undirected graph.

Author:

V. Levorato, J.-F. Lalande, P. Berthome

Constructor Summary

Constructors

Constructor and Description
Coloring(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> factory) Constructor of the Coloring algorithms.

Method Summary

Methods

Modifier and Type	Method and Description
int	chromaticNumberBjorklundHusfeldt(edu.uci.ics.jung.graph.Graph<V,E> g) Returns the chromatic number of a graph G.
int	chromaticNumberBodlaenderKratsch(edu.uci.ics.jung.graph.Graph<V,E> Ginit) Returns the chromatic number of a graph G.
java.util.Set<java.util.Set<V>>	graphColoring(edu.uci.ics.jung.graph.Graph<V,E> Ginit) Returns the chromatic number of a graph G.
java.util.Set<java.util.Set<V>>	greedyGraphColoring(edu.uci.ics.jung.graph.Graph<V,E> Ginit)

Methods inherited from class agape.algos.Algorithms

getEdgeFactory, getGraphFactory, getVertexFactory, setEdgeFactoy, setGraphFactoy, setVertexFactoy

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Coloring

public Coloring(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> factory)

Constructor of the Coloring algorithms. Needs a factory in order to create new graphs.

Parameters:

factory -

Method Detail

greedyGraphColoring

public java.util.Set<java.util.Set<V>> greedyGraphColoring(edu.uci.ics.jung.graph.Graph<V,E> Ginit)

Parameters:

Ginit - the graph

Returns:

a coloring assignment using a greedy algorithm that removes iteratively greedy MISs.

graphColoring

public java.util.Set<java.util.Set<V>> graphColoring(edu.uci.ics.jung.graph.Graph<V,E> Ginit)

Returns the chromatic number of a graph G. This method is based on the Bodlaender and Kratsch work ("An exact algorithm for graph coloring with polynomial memory" 2006). The algorithm solves the problem in PSPACE and in time O(5.283^n). This algorithm is limited to graphs having no more than 63 vertices.

Parameters:

Ginit - graph

Returns:

chromatic number of G

chromaticNumberBodlaenderKratsch

public int chromaticNumberBodlaenderKratsch(edu.uci.ics.jung.graph.Graph<V,E> Ginit)

Returns the chromatic number of a graph G. This method is based on the Bodlaender and Kratsch work ("An exact algorithm for graph coloring with polynomial memory" 2006). The algorithm solves the problem in PSPACE and in time O(5.283^n). This algorithm is limited to graphs having no more than 63 vertices.

Parameters:

Ginit - graph

Returns:

chromatic number of G

chromaticNumberBjorklundHusfeldt

public int chromaticNumberBjorklundHusfeldt(edu.uci.ics.jung.graph.Graph<V,E> g)

Returns the chromatic number of a graph G. The complexity of this algorithm is O(n^2.2^n) in time and O(n.2^n) in space. This method is based on the inclusion-exclusion algorithm proposed in A. Bjorklund and T. Husfeldt, “Inclusion--Exclusion Algorithms for Counting Set Partitions,” 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 575–582, 2006.

Parameters:

G - graph

Returns:

chromatic number of G