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
- Robertson, N. & Seymour, P.D. (1991), “Graph minors. X. Obstructions to tree-decomposition”, Journal of Combinatorial Theory 52 (2): 153-190, DOI 10.1016/0095-8956(91)90061-N.