Vis enkel innførsel

dc.contributor.authorVatshelle, Martineng
dc.date.accessioned2012-11-02T11:00:32Z
dc.date.available2012-11-02T11:00:32Z
dc.date.issued2012-09-03eng
dc.identifier.isbn978-82-308-2098-8 (print version)en_US
dc.identifier.urihttps://hdl.handle.net/1956/6166
dc.description.abstractThe main focus of this thesis is on using the divide and conquer technique to efficiently solve graph problems that are in general intractable. We work in the field of parameterized algorithms, using width parameters of graphs that indicate the complexity inherent in the structure of the input graph. We use the notion of branch decompositions of a set function introduced by Robertson and Seymour to define three new graph parameters, boolean-width, maximum matching-width (MM-width) and maximum induced matching-width (MIM-width). We compare these new graph width parameters to existing graph parameters by defining partial orders of width parameters. We focus on tree-width, branch-width, clique-width, module-width and rank-width, and include a Hasse diagram of these orders containing 32 graph parameters. We use the size of a maximum matching in a bipartite graph as a set function to define MM-width and show that MM-width never differs by more than a multiplicative factor 3 from tree-width. The main reason for introducing MM-width is that it simplifies the comparison between tree-width and parameters defined via branch decomposition of a set function. We use the logarithm of the number of maximal independent sets in a bipartite graph as set function to define boolean-width. We show that booleanwidth of a graph class is bounded if and only if rank-width is bounded, and show that the boolean-width of a graph can be as low as the logarithm of the rank-width of the graph. Given a decomposition of boolean-width k, we design FPT algorithms parameterized by k, for a large class of graph problems, whose runtime has a single exponential dependency in the boolean-width, i.e. O∗(2O(k2)). Moreover we solve Maximum Independent Set in time O∗(22k) and Minimum Dominating Set in time O∗(23k). These algorithms are in particular interesting in conjunction with the fact that many graph classes have boolean-width O(log(n)), e.g. interval graphs. MIM-width is defined using the size of a maximum induced matching in a bipartite graph as set function. The main reason to introduce MIM-width is that its value is lower than any of the other parameters, in particular MIMwidth is 1 on interval graphs, permutation graphs and convex graphs, and at most 2k on circular k-trapezoid graphs, k-polygon graphs, Dliworth k graphs and complements of k-degenerate graphs. We show that the FPT algorithms designed for boolean-width are XP algorithms when parameterized by MIMwidth, this shows that a large class of locally checkable vertex subset and vertex partitioning problems are polynomial time solvable on the mentioned graph classess with bounded MIM-width. We give exact algorithms to compute optimal decompositions for all the three new width parameters and report on the implementation of a heuristic for finding decompositions of low boolean-width.en_US
dc.language.isoengeng
dc.publisherThe University of Bergenen_US
dc.relation.haspartPaper I: Boolean-width of graphs. Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle.en_US
dc.relation.haspartPaper II: Graph Classes with Structured Neighborhoods and Algorithmic Applications. Remy Belmonte, Martin Vatshelle.en_US
dc.relation.haspartPaper III: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle.en_US
dc.relation.haspartPaper IV: Feedback Vertex Set on Graphs of Low Clique-width. Binh-Minh Bui-Xuan, Ondřej Suchý, Jan Arne Telle, Martin Vatshelle.en_US
dc.relation.haspartPaper V: Finding Good Decompositions for Dynamic Programming on Dense Graphs. Eivind Magnus Hvidevold, Sadia Sharmin, Jan Arne Telle, Martin Vatshelle.en_US
dc.titleNew Width Parameters of Graphsen_US
dc.typeDoctoral thesis
dc.rights.holderCopyright the author. All rights reserveden_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel