V
- the graph vertex typeE
- the graph edge typepublic class WeakChordalityInspector<V,E> extends Object
The following definitions of are equivalent:
The implementation in this class is based on: Lars Severin Skeide (2002) Recognizing weakly chordal graphs. Candidate Scientist Thesis in Informatics. Department of Informatics, University of Bergen, Norway. The terminology used in this implementation is consistent with the one used in this thesis.
Both the runtime complexity and space complexity of the algorithm implemented in this class is
$\mathcal{O}(|E|^2)$.
The inspected graph
is specified at the construction time and cannot be modified. When
the graph is modified externally, the behavior of the WeakChordalityInspector
is
undefined.
In the case the inspected graph in not weakly chordal, this inspector provides a certificate in the form of some hole or anti-hole. The running time of finding a hole is $\mathcal{O}(|V| + |E|)$ and of finding an anti-hole - $\mathcal{O}(|E|^2)$ in the worst case.
Constructor and Description |
---|
WeakChordalityInspector(Graph<V,E> graph)
Creates a weak chordality inspector for the
graph |
Modifier and Type | Method and Description |
---|---|
GraphPath<V,E> |
getCertificate()
Computes and returns the certificate in the form of a hole or anti-hole in the inspected
graph . |
boolean |
isWeaklyChordal()
Check whether the inspected
graph is weakly chordal. |
public boolean isWeaklyChordal()
graph
is weakly chordal. Note: this value is computed
lazily.graph
is weakly chordal, otherwise false.Copyright © 2019. All rights reserved.