wiki_research

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

treewidth_directed (401B)

      1 # Treewidth (directed)
      2 
      3 directed treewidth, when it is bounded then the k-[disjoint_paths] problem is tractable, cf [kawarabayashi2022directed]
      4 
      5 [kawarabayashi2022directed] shows that a [graph_directed] with high directed treewdith contains a [directed_grid] as [butterfly_minor]
      6 - polynomial bounds known [hatzel2019polynomial]
      7 
      8 Up: [treewidth]
      9 
     10 See also: [pathwidth_directed], [grid_minor_directed]