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