Computing pathwidth faster than 2n
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.
|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)|
|Fecha de publicación:||2009|
|Página de inicio:||324|
|Notas:||SCOPUS - SCOPUS|