Finding small-width connected path decompositions in polynomial time - Publikacja - MOST Wiedzy

Wyszukiwarka

Finding small-width connected path decompositions in polynomial time

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

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 128 razy

Publikacje, które mogą cię zainteresować

Meta Tagi