BORA - UiB

Bergen Open Research Archive

Computation of Treespan. A Generalization of Bandwidth to Treelike Structures

Bergen Open Research Archive

Show simple item record

dc.contributor.author Dregi, Markus Sortland
dc.date.accessioned 2012-09-28T11:31:01Z
dc.date.available 2012-09-28T11:31:01Z
dc.date.issued 2012-06-14
dc.date.submitted 2012-06-14 en
dc.identifier.uri http://hdl.handle.net/1956/6065
dc.description.abstract Motivated by a search game, Fomin, Heggernes and Telle [Algorithmica, 2005] defined the graph parameter treespan, a generalization of the well studied parameter bandwidth. Treespan is the maximum number of appearances of a vertex in an ordered tree decomposition, i.e. a tree decomposition intro- ducing at most one new vertex in each bag. In this thesis, we investigate the computational tractability of the problem Treespan, which aims to decide whether the treespan of a given graph is at most a given integer k. First we introduce a new perspective to the problem, with an equivalent parameter which we call adjacencyspan. It provides, in our opinion, a clearer under- standing of the nature of the problem. We provide structural results related to adjacencyspan, and combine these with dynamic programming to solve Treespan in polynomial time for fixed values of k and hence prove the problem to be in XP. Fomin et al. [Al- gorithmica, 2005] asked whether Treespan is polynomial time solvable for trees of degree higher than 3 as their final open problem. We solve this problem by proving Treespan to be polynomial time solvable for trees of bounded maximum degree d, for every fixed d. In the area of fixed parame- ter tractability we give a polynomial kernel for Treespan parameterized by both the required treespan and the vertex cover number of the input graph. It is a classical result, first proven by Lenstra [Mathematics of Operations Research, 1983], that p-Integer Linear Programming Feasibility is fixed parameter tractable. In his book Invitation to Fixed-Parameter Al- gorithms", Niedermeier specifically asks for more applications of this result. In this thesis we provide another application by using it to obtain a fixed parameter tractable algorithm for Treespan parameterized by the vertex cover number. The thesis do not only have theoretical implications, but we give algorithms that by far outperform previously known algorithms in practical terms. eng
dc.format.extent 762982 bytes en
dc.format.mimetype application/pdf en
dc.language.iso eng eng
dc.publisher The University of Bergen eng
dc.rights Copyright the author. All rights reserved eng
dc.subject Treespan eng
dc.subject Fixed parameter tractability eng
dc.subject Bandwidth eng
dc.subject Algorithms eng
dc.title Computation of Treespan. A Generalization of Bandwidth to Treelike Structures eng
dc.type Master thesis eng
dc.type.degree Master i Informatikk en
dc.type.course INF399 eng
dc.subject.archivecode Mastergrad en
dc.subject.nus 754199 en
dc.type.program MAMN-INF eng


Files in this item

 

This item appears in the following Collection(s)

Show simple item record

Search BORA


Browse

My Account