We present an algorithmic framework (including a single data structure) that is extended into linear-time algorithms to solve several NP-complete graph problems (i.e., INDEPENDENT SET, M AXIMUM CUT, GRAPH COLORING, HAMILTONIAN CYCLE, and DISJOINT PATHS). The linearity is achieved assuming the provision of a branch decomposition of the instance graph. We then modify the framework to create a multithreaded framework that uses the existing problem-specific extensions without any revision. Computational results for the serial and parallel algorithms are provided. In addition, we present a graphical package called JPAD that can display a graph and branch decomposition, show their relationship to each other, and be extended to rim and display the progress and results of algorithms on graphs or on branch decompositions.
| Identifer | oai:union.ndltd.org:RICE/oai:scholarship.rice.edu:1911/18516 |
| Date | January 2003 |
| Creators | Christian, William Anderson, Jr |
| Contributors | Dean, Nathaniel, Cook, William J. |
| Source Sets | Rice University |
| Language | English |
| Detected Language | English |
| Type | Thesis, Text |
| Format | 108 p., application/pdf |
Page generated in 0.0017 seconds