Treewidth

Treewidth and tree decompositions. More...

## Classes

class | regina::TreeBag
| Represents a single bag in a tree decomposition. More...
class | regina::TreeDecomposition
| Represents a tree decomposition of a graph. More...

## Typedefs

typedef TreeBag | regina::NTreeBag
| Deprecated typedef for backward compatibility. More...
typedef TreeDecomposition | regina::NTreeDecomposition
| Deprecated typedef for backward compatibility. More...

## Enumerations

enum | regina::TreeDecompositionAlg { regina::TD_UPPER = 0x0001, regina::TD_UPPER_GREEDY_FILL_IN = 0x0001 }
| Indicates which algorithm should be used to compute a tree decomposition of a graph. More...
enum | regina::BagComparison { regina::BAG_EQUAL = 0, regina::BAG_SUBSET = -1, regina::BAG_SUPERSET = 1, regina::BAG_UNRELATED = 2 }
| Indicates the relationship between two bags in a tree decomposition. More...
enum | regina::NiceType { regina::NICE_INTRODUCE = 1, regina::NICE_FORGET = 2, regina::NICE_JOIN = 3 }
| Used to indicate the type of each bag in a nice tree decomposition. More...

## Detailed Description

Treewidth and tree decompositions.

## Typedef Documentation

## NTreeBag

typedef TreeBag regina::NTreeBag

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
  The class NTreeBag has now been renamed to TreeBag.

## NTreeDecomposition

typedef TreeDecomposition regina::NTreeDecomposition

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
  The class NTreeDecomposition has now been renamed to TreeDecomposition.

## Enumeration Type Documentation

## BagComparison

enum regina::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

enum regina::NiceType

Used to indicate the type of each bag in a nice tree decomposition.

A nice tree decomposition is produced by calling TreeDecomposition::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 TreeDecomposition::makeNice() for further details, including how TreeBag::type() and TreeBag::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

enum regina::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.

Copyright © 1999-2016, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).