The notions of pathwidth and the closely related treewidth have become more and more important recently. The importance lies not only in theory but also in practice. Theoretically, lots of NP-hard problems become polynomially solvable when restricted in graphs with bounded pathwidth (or treewidth). Practically, pathwidth and treewidth have significant applications in many different fields such as searching games, VLSI design, matrix computation, etc. Computing pathwidth is an NP-complete problem for general graphs, but polynomially solvable for treewidth-bounded graphs. However, there is no known practical algorithm to compute pathwidth for treewidth-bounded graphs. In this dissertation, a new algorithm for computing pathwidth and finding an optimal pathwidth-decomposition for treewidth-bounded graph is presented. This algorithm uses an interval completion technique and the branch-and-bound method to make the pathwidth computation process more efficient, practical, and easy to implement. It can also be easily converted to a parallel algorithm. The data structure for implementing this algorithm is presented, and some computational results are shown. Some heuristic methods to approximate pathwidth for general graphs are also given, especially for series-parallel graphs.
| Identifer | oai:union.ndltd.org:RICE/oai:scholarship.rice.edu:1911/18662 |
| Date | January 2004 |
| Creators | Li, Ming |
| Contributors | Dean, Nathaniel |
| Source Sets | Rice University |
| Language | English |
| Detected Language | English |
| Type | Thesis, Text |
| Format | 104 p., application/pdf |
Page generated in 0.0017 seconds