nl.uu.cs.treewidth.algorithm
Class AllStartMinorMinWidth_QuickBB<D extends GraphInput.InputData>
java.lang.Object
nl.uu.cs.treewidth.algorithm.AllStartMinorMinWidth_QuickBB<D>
public class AllStartMinorMinWidth_QuickBB<D extends GraphInput.InputData>
- extends java.lang.Object
The algorithm repeativly contracts the lowest degree vertex with a lowest degree neighbor.
The lowerbound is the maximum degree of the selected lowest degree vertices at the time of contraction.
This algorithm is optimized to be used with the QuickBB algorithm.
It does not really contract the edges from the graph, but uses a copy of the neighbors of every vertex.
The 'MinorMinWidth' lower bound.
Reference: A Complete Anytime Algorithm for Treewidth
Vibhav Gogate and Rina Dechter
- Author:
- tw team
Constructor Summary |
AllStartMinorMinWidth_QuickBB()
Starts out as a lowerbound of -infty; improved to the mindegree
lowerbound once run() is called. |
Methods inherited from class java.lang.Object |
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
AllStartMinorMinWidth_QuickBB
public AllStartMinorMinWidth_QuickBB()
- Starts out as a lowerbound of -infty; improved to the mindegree
lowerbound once run() is called.
getName
public java.lang.String getName()
setInput
public void setInput(NGraph<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> g)
run
public void run()
contractEdge
public void contractEdge(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1,
NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v2)
removeVertex
public void removeVertex(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1)
getLowerBound
public int getLowerBound()