From Pathwidth to Connected Pathwidth

DOI10.1137/110826424zbMath1261.05102OpenAlexW3102587977MaRDI QIDQ4915196

Dariusz Dereniowski

Publication date: 9 April 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3031/

zbMATH Keywords

pathwidthgraph searchingconnected searchingfugitive search gamesconnected pathwidth

Mathematics Subject Classification ID

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

Related Items (14)

A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Contraction obstructions for connected graph searching ⋮ A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth ⋮ Jumping robbers in digraphs ⋮ Connected search for a lazy robber ⋮ Unnamed Item ⋮ The complexity of minimum-length path decompositions ⋮ Exclusive graph searching ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ On-line search in two-dimensional environment ⋮ Searching by heterogeneous agents ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Zero-visibility cops and robber and the pathwidth of a graph ⋮ Distributed graph searching with a sense of direction

This page was built for publication: From Pathwidth to Connected Pathwidth