Class ColorRefinementAlgorithm<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    VertexColoringAlgorithm<V>

    public class ColorRefinementAlgorithm<V,​E>
    extends Object
    implements VertexColoringAlgorithm<V>
    Color refinement algorithm that finds the coarsest stable coloring of a graph based on a given alpha coloring as described in the following paper: C. Berkholz, P. Bonsma, and M. Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems, 60(4), p581--614, 2017.

    The complexity of this algorithm is $O((|V| + |E|)log |V|)$.

    Author:
    Christoph GrĂ¼ne, Daniel Mock, Oliver Feith
    • Constructor Detail

      • ColorRefinementAlgorithm

        public ColorRefinementAlgorithm​(Graph<V,​E> graph,
                                        VertexColoringAlgorithm.Coloring<V> alpha)
        Construct a new coloring algorithm.
        Parameters:
        graph - the input graph
        alpha - the coloring on the graph to be refined
      • ColorRefinementAlgorithm

        public ColorRefinementAlgorithm​(Graph<V,​E> graph)
        Construct a new coloring algorithm.
        Parameters:
        graph - the input graph