Branch-decomposition

Branch-decomposition

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 T_1 and T_2. These trees induces a bipartition (E_1,E_2) of E which is called an e-separation.

Widths

The width of an "e-separation" is the number of vertices of G incident to an edge of E_1 and an edge of E_2.

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

References

*citation
last1 = Robertson | first1 = N.
last2 = Seymour | first2 = P.D.
title = Graph minors. X. Obstructions to tree-decomposition
journal = Journal of Combinatorial Theory
volume = 52 | issue = 2 | year = 1991 | pages = 153-190 | doi = 10.1016/0095-8956(91)90061-N
.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Decomposition — For other uses, see Decomposition (disambiguation). A mummified rat. Stages of death Pallor mortis Algor mortis …   Wikipedia

  • Tree decomposition — A graph with eight vertices, and a tree decomposition of it onto a tree with six nodes. Each graph edge connects two vertices that are listed together at some tree node, and each graph vertex is listed at the nodes of a contiguous subtree of the… …   Wikipedia

  • Polar decomposition — In mathematics, particularly in linear algebra and functional analysis, the polar decomposition of a matrix or linear operator is a factorization analogous to the polar form of a nonzero complex number z where r is the absolute value of z (a… …   Wikipedia

  • Manifold decomposition — In topology, a branch of mathematics, a manifold M may be decomposed or split by writing M as a combination of smaller pieces. When doing so, one must specify both what those pieces are and how they are put together to form M. Manifold… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Graphe (mathématiques) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Théorie des graphes — Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une théorie informatique et mathématique. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette… …   Wikipédia en Français

  • Dominating set — For Dominator in control flow graphs, see Dominator (graph theory). Dominating sets (red vertices). In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is joined to at… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”