From pathwidth to connected pathwidth

DOI10.4230/LIPICS.STACS.2011.416MaRDI QIDQ3113706zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski

Publication date 23 January 2012

Full work available at URL https://arxiv.org/abs/1007.1269, http://subs.emis.de/LIPIcs/frontdoor_59c3.html

zbMATH Keywords

connected pathwidthconnected searchingfugitive search gamesgraph searchingpathwidth

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph designs and isomorphic decomposition (05C51) Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: It is proven that the connected pathwidth of any graph $G$ is at most $2cdotpw(G)+1$, where $pw(G)$ is the pathwidth of $G$. The method is constructive, i.e. it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(d{k}^2)$, where $d$ is the number of `bags' in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality $csn(G)leq2sn(G)+3$, where $csn(G)$ and $sn(G)$ are the connected search number and the search number of $G$. Moreover, the algorithm presented in this work can be used to convert a given search strategy using $k$ searchers into a (monotone) connected one using $2k+3$ searchers and starting at an arbitrary homebase.

Recommendations

• From pathwidth to connected pathwidth
• Finding small-width connected path decompositions in polynomial time
• Connected Treewidth and Connected Graph Searching
• A linear fixed parameter tractable algorithm for connected pathwidth
• scientific article; zbMATH DE number 176249

Cited in

(9)

• Approximate search strategies for weighted trees
• Finding small-width connected path decompositions in polynomial time
• Connected Treewidth and Connected Graph Searching
• From pathwidth to connected pathwidth
• A linear fixed parameter tractable algorithm for connected pathwidth
• Connected graph searching
• Connected searching of weighted trees
• A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
• Monotony properties of connected visible graph searching

This page was built for publication: From pathwidth to connected pathwidth

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