Searching for Optimal Caterpillars in General and Bounded Treewidth Graphs

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Dinneen, M en Khosravani Moghadam, M en 2011-10-21T00:23:05Z en 2011 en
dc.identifier.uri en
dc.description.abstract In this thesis we are interested in optimization problems on caterpillar trees. A caterpillar is a tree with this property that if one removes its leaves only a path is left. The majority of this thesis is devoted to studying the Minimum Spanning Caterpillar Problem (MSCP). An instance of the MSCP is a graph with dual costs over its edges. In the MSCP our goal is to find a caterpillar tree that spans the input graph with the smallest overall cost. The cost of the caterpillar is the sum of the cost of its edges, where each edge takes one of two costs based on its role as a leaf edge or an internal one. We first show that the problem of finding a spanning caterpillar in a graph is NP-complete. As another result on the hardness of the MSCP, we show that there is no f (n)-approximation algorithm for the MSCP unless P = NP. Here f (n) is any polynomial-time computable function of n, the number of nodes of a graph. Then we introduce a quadratic integer programming formulation for the MSCP. By using the Gomory cutting method iteratively, we show that one can find a near optimal solution. We then show that our integer programming formulation can be transformed to a semi-definite programming problem. A parametrized algorithm that finds an optimal solution for the MSCP in bounded treewidth graphs is given in Chapter 4. Our algorithm is fast and practical for outer-planar, series parallel, Halin graphs and other graphs with small treewidth. en
dc.publisher ResearchSpace@Auckland en
dc.relation.ispartof PhD Thesis - University of Auckland en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. en
dc.rights.uri en
dc.rights.uri en
dc.title Searching for Optimal Caterpillars in General and Bounded Treewidth Graphs en
dc.type Thesis en The University of Auckland en Doctoral en PhD en
dc.rights.holder Copyright: The author en
pubs.elements-id 234143 en
pubs.record-created-at-source-date 2011-10-21 en

Full text options

This item appears in the following Collection(s)

Show simple item record Except where otherwise noted, this item's license is described as


Search ResearchSpace

Advanced Search