Lower bounds on the pathwidth of some grid-like graphs
From MaRDI portal
Publication:2476243
DOI10.1016/j.dam.2007.02.006zbMath1137.05069MaRDI QIDQ2476243
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
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