Show simple item record

dc.contributor.authorInkmann, Torstenen_US
dc.date.accessioned2008-06-10T20:38:38Z
dc.date.available2008-06-10T20:38:38Z
dc.date.issued2007-12-19en_US
dc.identifier.urihttp://hdl.handle.net/1853/22583
dc.description.abstractThe tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a tree structure. In this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface. In the first part of this thesis we develop a geometric description of tangles in graphs embedded on a fixed surface (tangles are the obstructions for low branch-width), generalizing a result of Robertson and Seymour. We use this result to establish a relationship between the branch-width of an embedded graph and the carving-width of an associated graph, generalizing a result for the plane of Seymour and Thomas. We also discuss how these results relate to the polynomial-time algorithm to determine the branch-width of planar graphs of Seymour and Thomas, and explain why their method does not generalize to surfaces other than the sphere. We also prove a result concerning the class C_2k of minor-minimal graphs of branch-width 2k in the plane, for an integer k at least 2. We show that applying a certain construction to a class of graphs in the projective plane yields a subclass of C_2k, but also show that not all members of C_2k arise in this way if k is at least 3. The last part of the thesis is concerned with applications of graphs of bounded tree-width to the Traveling Salesman Problem (TSP). We first show how one can solve the separation problem for comb inequalities (with an arbitrary number of teeth) in linear time if the tree-width is bounded. In the second part, we modify an algorithm of Letchford et al. using tree-decompositions to obtain a practical method for separating a different class of TSP inequalities, called simple DP constraints, and study their effectiveness for solving TSP instances.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectTree-decompositionsen_US
dc.subjectTSPen_US
dc.subjectBranch-widthen_US
dc.subjectGraphs on surfacesen_US
dc.subjectGraph theoryen_US
dc.subjectBranch-decompositionsen_US
dc.subject.lcshDecomposition method
dc.subject.lcshGraph theory
dc.subject.lcshTraveling-salesman problem
dc.subject.lcshProgramming (Mathematics)
dc.subject.lcshCombinatorial optimization
dc.titleTree-based decompositions of graphs on surfaces and applications to the traveling salesman problemen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Thomas, Robin; Committee Co-Chair: Cook, William J.; Committee Member: Dvorak, Zdenek; Committee Member: Parker, Robert G.; Committee Member: Yu, Xingxingen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record