Search
Abstract
A connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game.
Citations
-
3
CrossRef
-
0
Web of Science
-
3
Scopus
Authors (3)
-
Paweł Rzążewski
- Warsaw University of Technology, Faculty of Mathematics and Information Science
Cite as
Full text
download paper
downloaded 21 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2019.03.039
- License
- Copyright (2019 Elsevier B.V.)
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 794,
pages 85 - 100,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2019
- Bibliographic description:
- Dereniowski D., Osula D., Rzążewski P.: Finding small-width connected path decompositions in polynomial time// THEORETICAL COMPUTER SCIENCE -Vol. 794, (2019), s.85-100
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2019.03.039
- Verified by:
- Gdańsk University of Technology
seen 124 times