|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnl.uu.cs.treewidth.algorithm.MaximumMinimumDegree<D>
public class MaximumMinimumDegree<D extends GraphInput.InputData>
The degeneracity of a graph is a lower bound for treewidth. This is the maximum over all subgraphs of G of the minimum degree. It can be computed as follows: repeatedly remove the vertex of minimum degree. The maximum degree of a vertex at time of removal is the degeneracy. Reference: Treewidth: Computational Experiments (Koster, Bodlaender, and van Hoesel)
Nested Class Summary |
---|
Nested classes/interfaces inherited from interface nl.uu.cs.treewidth.algorithm.LowerBound |
---|
LowerBound.Creator |
Constructor Summary | |
---|---|
MaximumMinimumDegree()
Starts out as a lowerbound of -infty; improved to the mindegree lowerbound once run() is called. |
Method Summary | |
---|---|
int |
getLowerBound()
|
java.lang.String |
getName()
Every algorithm has a name. |
void |
run()
Does the actual computation of the algorithm. |
void |
setInput(NGraph<D> g)
Sets the input the algorithm will run on. |
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public MaximumMinimumDegree()
Method Detail |
---|
public java.lang.String getName()
Algorithm
getName
in interface Algorithm<D extends GraphInput.InputData>
public void setInput(NGraph<D> g)
Algorithm
setInput
in interface Algorithm<D extends GraphInput.InputData>
g
- The graph in standard graph format.public void run()
Algorithm
run
in interface Algorithm<D extends GraphInput.InputData>
public int getLowerBound()
getLowerBound
in interface LowerBound<D extends GraphInput.InputData>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |