Lower bounds on the pathwidth of some grid-like graphs
From MaRDI portal
Publication:2476243
DOI10.1016/J.DAM.2007.02.006zbMATH Open1137.05069OpenAlexW2066946142MaRDI QIDQ2476243FDOQ2476243
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Graph searching and a min-max theorem for tree-width
- Min Cut is NP-complete for edge weighted trees
- A partial k-arboretum of graphs with bounded treewidth
- Searching and pebbling
- Recontamination does not help to search a graph
- The vertex separation number of a graph equals its path-width
- Searching and sweeping graphs: a brief survey
- Title not available (Why is that?)
Cited In (15)
- Fast searching games on graphs
- On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
- The zero-visibility cops and robber game on graph products
- Bandwidth and pathwidth of three-dimensional grids
- On-line search in two-dimensional environment
- Searching for an intruder on graphs and their subdivisions
- Bounding the search number of graph products
- A cops and robber game in multidimensional grids
- Enumerating Hamiltonian cycles
- On the stab number of rectangle intersection graphs
- Many-to-many two-disjoint path covers in cylindrical and toroidal grids
- Standard directed search strategies and their applications
- On the treewidth of toroidal grids
- Security number of grid-like graphs
- Tight bounds for linkages in planar graphs
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)
