Show simple item record

dc.contributor.advisor Cook, William J.
dc.creatorHicks, Illya VaShun
dc.date.accessioned 2009-06-04T06:40:51Z
dc.date.available 2009-06-04T06:40:51Z
dc.date.issued 2000
dc.identifier.urihttps://hdl.handle.net/1911/19507
dc.description.abstract 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.
dc.format.extent 104 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectMathematics
Operations research
dc.title Branch decompositions and their applications
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Operations Research
thesis.degree.discipline Natural Sciences
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation Hicks, Illya VaShun. "Branch decompositions and their applications." (2000) Diss., Rice University. https://hdl.handle.net/1911/19507.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record