V
- the graph vertex typeE
- the graph edge typepublic class ChordalGraphMinimalVertexSeparatorFinder<V,E> extends Object
In the context of this implementation following definitions are used:
Let $\sigma = (v_1, v_2, \dots, v_n)$ be some perfect elimination order (peo) of the graph $G = (V, E)$. The induced graph on vertices $(v_1, v_2, \dots, v_i)$ with respect to peo $\sigma$ is denoted as $G_i$. The predecessors set of vertex $v$ with respect to peo $\sigma$ is denoted as $N(v, \sigma)$. A set $B$ is called a base set with respect to $\sigma$, is there exist some vertex $v$ with $t = \sigma(v)$ such that $N(v, \sigma) = B$ and B is not a maximal clique in $G_{t-1}$. The vertices which satisfy conditions described above are called dependent vertices with respect to $\sigma$. The cardinality of the set of dependent vertices is called a multiplicity of the base set $B$. The multiplicity of a minimal vertex separator indicates the number of different pairs of vertices separated by it.The definitions of a base set and a minimal vertex separator in the context of chordal graphs are equivalent.
For more information on the topic see: Kumar, P. Sreenivasa & Madhavan, C. E. Veni. (1998). Minimal vertex separators of chordal graphs. Discrete Applied Mathematics. 89. 155-168. 10.1016/S0166-218X(98)00123-1.
The running time of the algorithm is $\mathcal{O}(\omega(G)(|V| + |E|))$, where $\omega(G)$ is the size of a maximum clique of the graph $G$.
ChordalityInspector
Constructor and Description |
---|
ChordalGraphMinimalVertexSeparatorFinder(Graph<V,E> graph)
Creates new
ChordalGraphMinimalVertexSeparatorFinder instance. |
Modifier and Type | Method and Description |
---|---|
Set<Set<V>> |
getMinimalSeparators()
Computes a set of all minimal separators of the
graph and returns it. |
Map<Set<V>,Integer> |
getMinimalSeparatorsWithMultiplicities()
Computes a mapping of all minimal vertex separators of the
graph and returns it. |
public ChordalGraphMinimalVertexSeparatorFinder(Graph<V,E> graph)
ChordalGraphMinimalVertexSeparatorFinder
instance. The
ChordalityInspector
used in this implementation uses the
MaximumCardinalityIterator
iteratorgraph
- the graph minimal separators to search inpublic Set<Set<V>> getMinimalSeparators()
graph
and returns it. Returns null if
the graph
isn't chordal.graph
isn't chordalpublic Map<Set<V>,Integer> getMinimalSeparatorsWithMultiplicities()
graph
and returns it.
Returns null if the graph
isn't chordal.graph
isn't chordalCopyright © 2018. All rights reserved.