Lower bounds on the pathwidth of some grid-like graphs

DOI10.1016/J.DAM.2007.02.006MaRDI QIDQ2476243zbMATH OpenOpenAlexFDO

Authors 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

lower boundspathwidthcylindersgridstorivertex separationnode search number

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 176249
• Pathwidth and searching in parameterized threshold graphs
• On the treewidth of toroidal grids
• Bandwidth and pathwidth of three-dimensional grids
• Parameterized and Exact Computation

Cites work

• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Min Cut is NP-complete for edge weighted trees
• Recontamination does not help to search a graph
• Searching and pebbling
• Searching and sweeping graphs: a brief survey
• The vertex separation number of a graph equals its path-width

Cited in

(15)

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

This page was built for publication: Lower bounds on the pathwidth of some grid-like graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476243)