EUVIMEDEUVIMED entdecken
Crossref

Tangles are Decided by Weighted Vertex Sets

Christian Elbracht, Jakob Kneip, Maximilian Teegen

Advances in Combinatorics · 2020

DOI: 10.19086/aic.13691 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Advances in Combinatorics, 2020. Verfasst von Christian Elbracht und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Tree-like decompositions play an important role both in structural combinatorics and algorithm design. The most well-known are [tree decompositions](https://en.wikipedia.org/wiki/Tree_decomposition) of graphs, which are of key importance in the Graph Minor Project of Robertson and Seymour as well as in algorithm design. The minimum width of a tree decomposition is the [treewidth](https://en.wikipedia.org/wiki/Treewidth) of a graph; this parameter captures how closely the global structure of a graph resembles a tree. In particular, a graph has treewidth one if and only if each of its components is a tree. Treewidth has a strong [duality property](https://en.wikipedia.org/wiki/Duality_(optimization)) in the sense of mathematical optimization: the minimum treewidth of a graph is equal to the maximum order of a [bramble](https://en.wikipedia.org/wiki/Bramble_(graph_theory)) increased by one; a bramble is a collection of touching connected subgraphs that cannot be hit by a small set of vertices. [Branchwidth](https://en.wikipedia.org/wiki/Branch-decomposition), which is linearly related to treewidth, is another important width parameter, and its dual parameter is the maximum order of a *tangle*, an object that is more amenable to generalizations to other combinatorial structures than a bramble. Informally speaking, a tangle picks for every separation a small part in a way that small parts of any three separations do not cover the whole structure. In the case of graphs, a tangle of order $k$ concerns vertex $k$-separations, i.e., pairs of subsets of the vertex set such that the union of the two subsets is the whole vertex set, the intersection has size at most $k$ and every edge is in one of the subsets. The main result of the article asserts that every tangle of a graph can be obtained by assigning weights to the vertices so that the small part of every $k$-separation is the one of smaller weight.

Zitieren

APA

Elbracht, C., Kneip, J., & Teegen, M. (2020). Tangles are Decided by Weighted Vertex Sets. Advances in Combinatorics. https://doi.org/10.19086/aic.13691

Vancouver

Elbracht C, Kneip J, Teegen M. Tangles are Decided by Weighted Vertex Sets. Advances in Combinatorics. 2020. doi:10.19086/aic.13691

BibTeX
@article{Elbracht2020,
  author = {Elbracht, Christian and Kneip, Jakob and Teegen, Maximilian},
  title = {Tangles are Decided by Weighted Vertex Sets},
  journal = {Advances in Combinatorics},
  year = {2020},
  doi = {10.19086/aic.13691}
}
Kostenlos starten →