Lower bounds on the pathwidth of some grid-like graphs

DOI10.1016/j.dam.2007.02.006zbMath1137.05069OpenAlexW2066946142MaRDI 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

gridslower boundspathwidthcylinderstorivertex separationnode search number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item