Finding small-width connected path decompositions in polynomial time - Publication - Bridge of Knowledge

Search

Finding small-width connected path decompositions in polynomial time

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

Cite as

Full text

download paper
downloaded 0 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 78 times

Recommended for you

Meta Tags