Metraipolis › archive › dc_975af7992f53
Branch-decomposition — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Branch-decomposition
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-07T18:09:17.016Z
- SHA-256 of the archived text
9f8eead0ec90815bccdb44f2f9eacfa3a1c64e6db88ff3b6261b671fe41bb09d- Stable URL of this page
https://metraipolis.com/documento/dc_975af7992f53
How to cite
Branch-decomposition — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Branch-decomposition (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_975af7992f53 (Metraipolis archive dc_975af7992f53, sha256 9f8eead0ec90815bccdb44f2f9eacfa3a1c64e6db88ff3b6261b671fe41bb09d)
BibTeX
@misc{dc975af7992f53,
title = {Branch-decomposition — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Branch-decomposition},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_975af7992f53; sha256 9f8eead0ec90815bccdb44f2f9eacfa3a1c64e6db88ff3b6261b671fe41bb09d},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Branch-decomposition. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In graph theory, a branch-decomposition of an undirected graph G is a hierarchical clustering of the edges of G, represented by an unrooted binary tree T with the edges of G as its leaves. Removing any edge from T partitions the edges of G into two subgraphs, and the width of the decomposition is the maximum number of shared vertices of any pair of subgraphs formed in this way. The branchwidth of G is the minimum width of any branch-decomposition of G. Branchwidth is closely related to tree-width: for all graphs, both of these numbers are within a constant factor of each other, and both quantities may be characterized by forbidden minors. And as with treewidth, many graph optimization problems may be solved efficiently for graphs of small branchwidth. However, unlike treewidth, the branchwidth of planar graphs may be computed exactly, in polynomial time. Branch-decompositions and branchwidth may also be generalized from graphs to matroids. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»). Fonte: Wikipedia in inglese, voce «Branch-decomposition» — https://en.wikipedia.org/wiki/Branch-decomposition Wikidata Q4956329: «term in graph theory» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4956329 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Branch-decomposition?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1340875700, consultata il 2026-11-07T18:05:03.829Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 8c9225c4fb1ddd8a427e6463ac6ffaf6b912bde4a3f269f118b3c19fed797e32