Linear-time algorithms for graphs with bounded branchwidth

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.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

2003

Author dc:creator

• Christian, William Anderson, Jr

Advisors dc:contributor.advisor

• Dean, Nathaniel
• Cook, William J.

• Mathematics
• Industrial engineering
• Computer science

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/18516

OAI identifier oai:identifier

oai:repository.rice.edu:1911/18516