|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnl.uu.cs.treewidth.algorithm.GreedyFillIn<D>
public class GreedyFillIn<D extends GraphInput.InputData>
The GreedyFillIn algorithm computes a permutation and at the same time derives an upperbound.
It does this by eliminating the vertex for which we have to add the lowest number of edges
when we would eliminate the vertex. This is done until the graph is empty.
Reference paper: Treewidth Computations I. Upper Bounds, Hans L. Bodlaender and Arie M.C.A. Koster (to appear).
Nested Class Summary | |
---|---|
class |
GreedyFillIn.GreedyData
|
Constructor Summary | |
---|---|
GreedyFillIn()
|
|
GreedyFillIn(boolean checkDegreeZero)
|
Method Summary | |
---|---|
java.lang.String |
getName()
Every algorithm has a name. |
NVertexOrder<D> |
getPermutation()
|
int |
getUpperBound()
Returns the upperbound. |
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 GreedyFillIn()
public GreedyFillIn(boolean checkDegreeZero)
Method Detail |
---|
public NVertexOrder<D> getPermutation()
getPermutation
in interface Permutation<D extends GraphInput.InputData>
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 getUpperBound()
UpperBound
getUpperBound
in interface UpperBound<D extends GraphInput.InputData>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |