Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Computing Pathwidth Faster Than 2 n
verfasst von : Karol Suchan, Yngve Villanger
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Computing the
Pathwidth
of a graph is the problem of finding a tree decomposition of minimum width, where the decomposition tree is a path. It can be easily computed in
$\mathcal{O}^*(2^n)$
time by using dynamic programming over all vertex subsets. For some time now there has been an open problem if there exists an algorithm computing
Pathwidth
with running time
$\mathcal{O}^*(c^n)$
for
c
< 2. In this paper we show that such an algorithm with
c
= 1.9657 exists, and that there also exists an approximation algorithm and a constant
τ
such that an
opt
+
τ
approximation can be obtained in
$\mathcal{O}^*(1.89^ n)$
time.