Branch-decomposition

From Wikipedia, the free encyclopedia

In graph theory, the branch-decomposition of a graph G = (V,E) is a ternary tree T and a bijection from the set of the leaves of T into E, the set of edges of G. A ternary tree is a tree in which every vertex has degree 1 or 3.

For any edge e of T, the graph T / e is composed of two subtrees T1 and T2. These trees induces a bipartition (E1,E2) of E which is called an e-separation.

[edit] Widths

The width of an e-separation is the number of vertices of G incident to an edge of E1 and an edge of E2.

The width of a branch-decomposition is the maximum with of an e-separation.

The branchwidth of G is the minimum width of a branch-decomposition of G

[edit] References