wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

tree_decomposition_linked (558B)


      1 # Linked tree decomposition
      2 
      3 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
      4 
      5 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])
      6 
      7 Up: [tree_decomposition]
      8 
      9 Alias: linked tree decomposition, linked tree decompositions