commit 6d5088b61598ac5a21f336d7cf266ee0825c5d04
parent 4ea92467b8d880bf5202001f394d18118fa48e69
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Mon, 30 Jun 2025 21:34:06 +0200
commit with codex
Diffstat:
2 files changed, 10 insertions(+), 0 deletions(-)
diff --git a/tree_decomposition b/tree_decomposition
@@ -3,6 +3,7 @@
- [tree_decomposition_computing]
- [tree_decomposition_updating]
- [balancing_tree_decomposition]
+- [tree_decomposition_linked]
See also: [treewidth]
diff --git a/tree_decomposition_linked b/tree_decomposition_linked
@@ -0,0 +1,9 @@
+# Linked tree decomposition
+
+A [tree_decomposition] with the following extra property: for every integer k, for every two bags b and b', either there are k disjoint paths connecting the vertices of b and those of b', or there is a bag b'' on the path connecting b and b' that has cardinality <k
+
+Discussed in [erde2018unified] Definition 1.1, shown in [robertson1986graph5] to exist up to an exponential blowup in the [treewidth] only (Theorem 1.2 of [erde2018unified])
+
+Up: [tree_decomposition]
+
+Alias: linked tree decomposition, linked tree decompositions
