Branch decompositions and their applications

Many real-life problems can be modeled as optimization or decision problems on graphs. Also, many of those real-life problems are NP-hard. One traditional method to solve these problems is by branch and bound while another method is by graph decompositions. In the 1980's, Robertson and Seymour conceived of two new ways to decompose the graph in order to solve these problems. These ingenious ideas were only by-products of their work proving Wagner's Conjecture. A branch decomposition is one of these ideas. A paper by Arnborg, Lagergren and Seeseshowed that many NP-complete problems can be solved in polynomial time using divide and conquer techniques on input graphs with bounded branchwidth, but a paper by Seymour and Thomas proved that computing an optimal branch decomposition is also NP-complete. Although computing optimal branch decompositions is NP-complete, there is a plethora of theory about branchwidth and branch decompositions. For example, a paper by Seymour and Thomas offered a polynomial time algorithm to compute the branchwidth and optimal branch decomposition for planar graphs. This doctoral research is concentrated on constructing branch decompositions for graphs and using branch decompositions to solve NP-complete problems modeled on graphs. In particular, a heuristic to compute near-optimal branch decompositions is presented and the heuristic is compared to previous heuristics in the subject. Furthermore, a practical implementation of an algorithm given in a paper by Seymour and Thomas for computing optimal branch decompositions of planar graphs is implemented with the addition of heuristics to give the algorithm a "divide and conquer" design. In addition, this work includes a theoretical result relating the branchwidth of planar graphs to their duals, characterizations of branchwidth for Halin and chordal graphs. Also, this work presents an algorithm for minor containment using a branch decomposition and a parallel implementation of the heuristic for general graphs using p-threads.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

2000

Author dc:creator

• Hicks, Illya VaShun

Advisor dc:contributor.advisor

• Cook, William J.

• Mathematics
• Operations research

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/19507

OAI identifier oai:identifier

oai:repository.rice.edu:1911/19507