nl.uu.cs.treewidth.algorithm
Class AllStartMinorMinWidth_QuickBB<D extends GraphInput.InputData>

java.lang.Object
  extended by 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.
 
Method Summary
 void contractEdge(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1, NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v2)
           
 int getLowerBound()
           
 java.lang.String getName()
           
 void removeVertex(NVertex<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> v1)
           
 void run()
           
 void setInput(NGraph<nl.uu.cs.treewidth.algorithm.QuickBB.QuickBBData> g)
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AllStartMinorMinWidth_QuickBB

public AllStartMinorMinWidth_QuickBB()
Starts out as a lowerbound of -infty; improved to the mindegree lowerbound once run() is called.

Method Detail

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()