Package nl.uu.cs.treewidth.algorithm

Interface Summary
Algorithm<D extends GraphInput.InputData> Base interface for all algorithms.
Constructive<D extends GraphInput.InputData> Interface for algorithms that produce a tree decomposition.
Exact<D extends GraphInput.InputData> Interface for algorithms that calculate the exact treewidth.
LowerBound<D extends GraphInput.InputData> Interface for algorithms that compute a lowerbound.
LowerBound.Creator  
Permutation<D extends GraphInput.InputData>  
UpperBound<D extends GraphInput.InputData> Interface for algorithms that compute an upperbound.
 

Class Summary
AllStartLexBFS<D extends GraphInput.InputData> Triangulation by using the elimination scheme found by applying the LEX-P algorithm.
AllStartMaximumCardinalitySearch<D extends GraphInput.InputData> Triangulation by using the elimination scheme obtained by using the MCS (Maximum Cardinality Search) algorithm as given by Tarjan and Yannakakis.
AllStartMaximumCardinalitySearchMinimal<D extends GraphInput.InputData> Triangulation obtained by using the elimination scheme produced by the MCS (Maximum Cardinality Search) algorithm of Berry et al.
AllStartMaximumMinimumDegree<D extends GraphInput.InputData> The degeneracity of a graph is a lower bound for treewidth.
AllStartMaximumMinimumDegreePlusLeastC<D extends GraphInput.InputData> The MMD+ heuristic with the least-c contraction rul: when there is a tiebreaker, we contract such that the contracted vertices have the smallest number of common neighbors.
AllStartMinorMinWidth<D extends GraphInput.InputData> The algorithm repeativly contracts the lowest degree vertex with a lowest degree neighbor.
AllStartMinorMinWidth_QuickBB<D extends GraphInput.InputData> The algorithm repeativly contracts the lowest degree vertex with a lowest degree neighbor.
CliqueFinder<D extends GraphInput.InputData>  
GreedyDegree<D extends GraphInput.InputData> The GreedyDegree algorithm computes a permutation and at the same time derives an upperbound.
GreedyFillIn<D extends GraphInput.InputData> The GreedyFillIn algorithm computes a permutation and at the same time derives an upperbound.
LexBFS<D extends GraphInput.InputData> Triangulation by using the elimination scheme found by applying the LEX-P algorithm.
MaximumCardinalitySearch<D extends GraphInput.InputData> Triangulation by using the elimination scheme obtained by using the MCS (Maximum Cardinality Search) algorithm as given by Tarjan and Yannakakis.
MaximumCardinalitySearchMinimal<D extends GraphInput.InputData> Triangulation obtained by using the elimination scheme produced by the MCS (Maximum Cardinality Search) algorithm of Berry et al.
MaximumMinimumDegree<D extends GraphInput.InputData> The degeneracity of a graph is a lower bound for treewidth.
MaximumMinimumDegreePlusLeastC<D extends GraphInput.InputData> The MMD+ heuristic with the least-c contraction rul: when there is a tiebreaker, we contract such that the contracted vertices have the smallest number of common neighbors.
MaximumMinimumDegreePlusMaxD<D extends GraphInput.InputData> The MMD+Max-d: Maximum Minimum Degree Plus max-d: gives the maximum over the minimum degrees of the vertices in the graph.
MaximumMinimumDegreePlusMinD<D extends GraphInput.InputData> The MMD+Min-d: Maximum Minimum Degree Plus min-d: gives the maximum over the minimum degrees of the vertices in the graph.
MaximumMinimumDegreePlusMinD2 The MMD+Min-d: Maximum Minimum Degree Plus min-d: gives the maximum over the minimum degrees of the vertices in the graph.
MinDegree<D extends GraphInput.InputData> The 'minimum degree' lower bound: gives the minimum degree of a vertex in the graph.
MinorMinWidth<D extends GraphInput.InputData> Used graphstructure: NeighborHashSetGraph The 'MinorMinWidth' lower bound.
MinorMinWidth_QuickBB<D extends GraphInput.InputData> The 'MinorMinWidth' lower bound.
PermutationGuesser<D extends GraphInput.InputData>  
PermutationToTreeDecomposition<D extends GraphInput.InputData>  
PreProcessor<D extends GraphInput.InputData>  
QuickBB<D extends GraphInput.InputData> A branch and bound algorithm for treewidth, designed by Gogate and Dechter.
Ramachandramurthi<D extends GraphInput.InputData> The 'Ramachandramurthi' lower bound.
TreewidthDP<D extends GraphInput.InputData>