template<class EditableGraph>
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
class BALL::TreeWidthImplementation< EditableGraph >::QuickBB< Lowerbound, Upperbound >
This algorithm computes a perfect elimination order in a branch and bound approach. First it computes a greedy solution. Then it tries each vertex permutation and uses a lower bound algorithm to check, if this branch can be better than either the best found solution or a found permutation of the same vertices but in a different order. If not, the branch is bounded and the algorithm tries another permutation.
- Template Parameters
-
| Lowerbound | the lowerbound algorithm which should be used by this branch and bound algorithm |
| Upperbound | the greedy algorithm which is used to compute a initial solution |
Definition at line 316 of file treeWidth.h.
template<class EditableGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
A vertex IS simplicial, if its neighbourhood induces a clique. A vertex is ALMOST simplicial, it all but one of its neighbours induces a clique.
| Enumerator |
|---|
| NOT_SIMPLICIAL |
|
| ALMOST_SIMPLICIAL |
|
| IS_SIMPLICIAL |
|
Definition at line 324 of file treeWidth.h.
template<class EditableGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
Each vertex in the search tree is an elimination order. The root is an elimination order of length 0. It's children are elimination order of length 1 and so on. The leafs are elimination order of length n and define a tree decomposition. This algorithm searches the best solution (= permutation with minimal tree width) in this search tree. It computes the lowerbound for each vertex to get the mimimal tree width of the subtree, which is rooted in this vertex. Branches are bounded, if their lowerbound is higher than the tree width of the best found solution, or if there is another branch with a better tree width which eliminates the same vertices but in a different order. To speed up the computation, the algorithm uses a greedy solution as "template".
template<class EditableGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
Vertices which are simplicial or almost simplicial can be eliminated instantly. So this function is called at the begin of the algorithm to reduce the number of vertices and the length of the searched permutation. You could call this function in each branch&bound step, but testing the simpliciality is expensive. So this is done only one time in the algorithm.
template<class EditableGraph >
template<class Lowerbound = MinorMinWidth, class Upperbound = GreedyX<FillInHeuristic>>
the current upper bound. A branch is bound if it has a worse penalty than the upper bound. Each found solution gives a new upper bound. The greedy solution is the initial upper bound. The algorithm terminates if it's upper bound is equal to the lowerbound.
Definition at line 406 of file treeWidth.h.
1.8.3.1