Class ChordalGraphMaxCliqueFinder<V,​E>

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

    public class ChordalGraphMaxCliqueFinder<V,​E>
    extends java.lang.Object
    implements CliqueAlgorithm<V>
    Calculates a maximum cardinality clique 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 clique, this implementation relies on the ChordalityInspector to compute a perfect elimination order. The maximum clique 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