wiki_research

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

grid_minor (575B)

      1 # Grid minor extraction
      2 
      3 [theorem] about finding [grid_graph] as [graph_minor] of [graph_undirected] of high [treewidth]
      4 
      5 relevant [academic_papers]:
      6 - [lanzinger2022complexity]
      7 - [chekuri2016polynomial]
      8 - [chuzhoy2021towards] for tighter bounds on grid minor extraction
      9 - https://laxarchive.org/lax-17/ bound with exponent 8 on [laxarchive]
     10 
     11 used for [hardness] results, e.g., [grohe2007complexity]
     12 
     13 Up: [theorem] about [grid_graph]
     14 
     15 See also: [grid_minor_directed], [treewidth], [polynomial_grid_minor_theorem]
     16 
     17 Aliases: grid minor extraction, grid extraction, grid minors