Wyszukiwarka
Abstrakt
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.
Cytowania
-
3
CrossRef
-
0
Web of Science
-
3
Scopus
Autorzy (3)
-
Paweł Rzążewski
- Warsaw University of Technology, Faculty of Mathematics and Information Science
Cytuj jako
Pełna treść
pobierz publikację
pobrano 21 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2019.03.039
- Licencja
- Copyright (2019 Elsevier B.V.)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
THEORETICAL COMPUTER SCIENCE
nr 794,
strony 85 - 100,
ISSN: 0304-3975 - Język:
- angielski
- Rok wydania:
- 2019
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2019.03.039
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 124 razy