Class ChordalGraphIndependentSetFinder<V,​E>

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

    public class ChordalGraphIndependentSetFinder<V,​E>
    extends java.lang.Object
    implements IndependentSetAlgorithm<V>
    Calculates a maximum cardinality independent set in a chordal graph. A chordal graph is a simple graph in which all cycles of four or more vertices have a chord. A chord is an edge that is not part of the cycle but connects two vertices of the cycle. To compute the independent set, this implementation relies on the ChordalityInspector to compute a perfect elimination order. The maximum cardinality independent set for a chordal graph is computed in $\mathcal{O}(|V| + |E|)$ time. All the methods in this class are invoked in a lazy fashion, meaning that computations are only started once the method gets invoked.
    Author:
    Timofey Chudakov