### Computing pathwidth faster than 2n

### Abstract

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 |

DOI: |
10.1007/978-3-642-11269-0_27 |

Notas: | SCOPUS - SCOPUS |