Approximation of pathwidth of outerplanar graphs |
| |
| Authors: | Hans L Bodlaender Fedor V Fomin |
| |
| Institution: | a Institute of Information and Computing Sciences, Utrecht University, PO Box 80.089, 3508 TB Utrecht, The Netherlands;b Graduiertenkolleg des PaSCo, Heinz Nixdorf Institut and University of Paderborn, Fürstenallee 11, D-33102 Paderborn, Germany |
| |
| Abstract: | There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established. |
| |
| Keywords: | Pathwidth treewidth approximation algorithm outerplanar graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
