Treewidth and tree decompositions.
More...
Treewidth and tree decompositions.
§ BagComparison
Indicates the relationship between two bags in a tree decomposition.
Enumerator |
---|
BAG_EQUAL | Indicates that the two bags have identical contents.
|
BAG_SUBSET | Indicates that the first bag is a strict subset of the second.
|
BAG_SUPERSET | Indicates that the first bag is a strict superset of the second.
|
BAG_UNRELATED | Indicates that neither bag is a subset of the other.
|
§ NiceType
Used to indicate the type of each bag in a nice tree decomposition.
A nice tree decomposition is produced by calling NTreeDecomposition::makeNice(). As a result:
- every bag will be either an introduce bag, a forget bag, or a join bag, as defined below;
- the root bag will be a forget bag, and will be empty;
- every leaf bag will be an introduce bag, containing precisely one node.
See NTreeDecomposition::makeNice() for further details, including how NTreeBag::type() and NTreeBag::subtype() are defined for a nice tree decomposition.
Enumerator |
---|
NICE_INTRODUCE | Indicates an introduce bag.
An introduce bag has only one child bag. It contains all of the nodes in this child bag plus exactly one new node, and contains no other nodes besides these.
As a special case, a leaf bag (which has no child bags at all) is also considered to be an introduce bag. In this case, the leaf bag contains exactly one node.
|
NICE_FORGET | Indicates a forget bag.
A forget bag has only one child bag. It contains all of the nodes in this child bag except for exactly one missing node, and contains no other nodes besides these.
|
NICE_JOIN | Indicates a join bag.
A join bag has exactly two child bags, where the join bag and both of its child bags are all identical.
|
§ TreeDecompositionAlg
Indicates which algorithm should be used to compute a tree decomposition of a graph.
Additional algorithms may be added to this list in future versions of Regina.
Enumerator |
---|
TD_UPPER | Indicates that a fast upper bound algorithm should be used.
This does not promise to find a tree decomposition of smallest possible width (an NP-hard problem), but it does promise to run in small polynomial time.
This constant TD_UPPER indicates that the "most appropriate" upper bound algorithm should be used. This is a good choice for users who just want a good tree decomposition and want it quickly, without needing to know the details of how it was produced.
|
TD_UPPER_GREEDY_FILL_IN | Indicates that the greedy fill-in heuristic should be used.
This does not promise to find a tree decomposition of smallest possible width (an NP-hard problem), but it does promise to run in small polynomial time.
The greedy fill-in heuristic has been found experimentally to perform well on general graphs (T. van Dijk, J.-P. van den Heuvel and W. Slob, "Computing treewidth with LibTW", www.treewidth.com, 2006). Experimentation within Regina also suggests that it performs well in the setting of face pairing graphs of 3-manifold triangulations.
|