Computing pathwidth faster than 2n

Suchan K.; Villanger Y.


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 O*(2n) in 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 Path-width with running time 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 t such that an opt + t approximation can be obtained in O*(1.89n) time. © 2009 Springer-Verlag.

Más información

Título según SCOPUS: Computing pathwidth faster than 2n
Título de la Revista: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen: 5917
Editorial: Springer Verlag
Fecha de publicación: 2009
Página de inicio: 324
Página final: 335
Idioma: eng