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

java.lang.Object
  extended by nl.uu.cs.treewidth.algorithm.Ramachandramurthi<D>
All Implemented Interfaces:
Algorithm<D>, LowerBound<D>

public class Ramachandramurthi<D extends GraphInput.InputData>
extends java.lang.Object
implements LowerBound<D>

The 'Ramachandramurthi' lower bound. When G = (V;E) is a clique, the lowerbound equals the number of vertices minus 1; and when G is not a clique, the lowerbound equals the minimum over all pairs of non-adjacent vertices v, w, of the maximum of the degree of v and w. * Reference: The Structure and Number of Obstructions to Treewidth Siddharthan Ramachandramurthi

Author:
tw team

Nested Class Summary
 
Nested classes/interfaces inherited from interface nl.uu.cs.treewidth.algorithm.LowerBound
LowerBound.Creator
 
Constructor Summary
Ramachandramurthi()
          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()
          Method runs the algorithm and sets the lowerbound.
 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

Ramachandramurthi

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

Method Detail

getName

public java.lang.String getName()
Description copied from interface: Algorithm
Every algorithm has a name. This is for identification towards the user.

Specified by:
getName in interface Algorithm<D extends GraphInput.InputData>
Returns:
Name of the algorithm.

setInput

public void setInput(NGraph<D> g)
Description copied from interface: Algorithm
Sets the input the algorithm will run on.

Specified by:
setInput in interface Algorithm<D extends GraphInput.InputData>
Parameters:
g - The graph in standard graph format.

run

public void run()
Method runs the algorithm and sets the lowerbound.

Specified by:
run in interface Algorithm<D extends GraphInput.InputData>

getLowerBound

public int getLowerBound()
Specified by:
getLowerBound in interface LowerBound<D extends GraphInput.InputData>
Returns:
A valid lowerbound. See class documentation for details.