Lower bounds on the pathwidth of some grid-like graphs

DOI10.1016/j.dam.2007.02.006zbMath1137.05069MaRDI QIDQ2476243

Yanyan Li

Publication date: 18 March 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.02.006

zbMATH Keywords

grids; lower bounds; pathwidth; cylinders; tori; vertex separation; node search number

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Bounding the search number of graph products, On-line search in two-dimensional environment, Fast searching games on graphs, Enumerating Hamiltonian cycles, Bandwidth and pathwidth of three-dimensional grids, A cops and robber game in multidimensional grids, On the stab number of rectangle intersection graphs, On the treewidth of toroidal grids, Security number of grid-like graphs, Standard directed search strategies and their applications, Searching for an intruder on graphs and their subdivisions, Many-to-many two-disjoint path covers in cylindrical and toroidal grids, On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth, Tight Bounds for Linkages in Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Min Cut is NP-complete for edge weighted trees
• The vertex separation number of a graph equals its path-width
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Searching and pebbling
• Recontamination does not help to search a graph