We consider the problem of computing the branchwidth and an optimal branch decomposition
of a graph. Branch decompositions and branchwidth were introduced in
1991 by Robertson and Seymour and were used in the proof of Graph Minors Theorem
(GMT), a well known conjecture (Wagner's conjecture) in graph theory. The
notions of branchwidth and branch decompositions have been proved to be useful for
solving many NP-hard problems that have applications in fields such as graph theory,
network design, sensor networks and biology. Branch decompositions have been
utilized for problems such as the traveling salesman problem by Cook and Seymour,
general minor containment and the branchwidth problem by Hicks by means of the
relevant branch decomposition-based algorithms.
Branch decomposition-based algorithms are fixed parameter tractable algorithms
obtained by combining dynamic programming techniques with branch decompositions.
The running time and space of these algorithms strongly depend on the width
of the utilized branch decomposition. Thus, finding optimal or close to optimal branch
decompositions is very important for the efficiency of the branch decomposition-based
algorithms. Motivated by the vastness of the fields of application, we aim to increase
the efficiency of the branch decomposition-based algorithms by investigating effective techniques to find optimal branch decompositions.
We present three integer programming models for the branchwidth problem.
Two similar formulations are based on the relationship of branchwidth problem with
a special case of the Steiner tree packing problem. The third formulation is based on
the notion of laminar separations. We utilize upper and lower bounds obtained by
heuristic algorithms, reduction techniques and cutting planes to increase the efficiency
of our models. We use all three models for the branchwidth problem on hypergraphs as
well. We compare the performance of three models both on graphs and hypergraphs.
Furthermore we use the third model for rank-width problem and also offer a
heuristic for finding good rank decompositions. We provide computational results for
this problem, which can be a basis of comparison for future formulations.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/85936 |
| Date | 10 October 2008 |
| Creators | Ulusal, Elif |
| Contributors | Butenko, Sergiy I., Hicks, Illya V. |
| Publisher | Texas A&M University |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Dissertation, text |
| Format | electronic, born digital |
Page generated in 0.002 seconds