Searching for optimal caterpillars in general and bounded treewidth graphs

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Dinneen, Michael J en
dc.contributor.author Khosravani, Masoud en
dc.date.accessioned 2011-10-21T00:23:05Z en
dc.date.available 2011-10-21T00:23:05Z en
dc.date.issued 2011 en
dc.identifier.uri http://hdl.handle.net/2292/8360 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.relation.isreferencedby UoA2203810 en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.rights.uri http://creativecommons.org/licenses/by-nc-sa/3.0/nz/ en
dc.title Searching for optimal caterpillars in general and bounded treewidth graphs en
dc.type Thesis en
thesis.degree.discipline PhD--Computer Science en
thesis.degree.grantor The University of Auckland en
thesis.degree.level Doctoral en
thesis.degree.name PhD en
dc.rights.holder Copyright: The author en
pubs.organisational-group /Auckland en
pubs.organisational-group /Auckland/Faculty of Engineering en
pubs.organisational-group /Auckland/Faculty of Engineering/Electrical & Computer Engineer en
pubs.elements-id 234143 en
pubs.org-id Faculty of Engineering en
pubs.org-id Electrical & Computer Engineer en


Full text options

This item appears in the following Collection(s)

Show simple item record

http://creativecommons.org/licenses/by-nc-sa/3.0/nz/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc-sa/3.0/nz/

Share

Search ResearchSpace


Advanced Search

Browse