1. Approximating connectivity domination in weighted bounded-genus graphs
- Author
-
Éric Colin de Verdière, David Meierfrankenfeld, Philip N. Klein, Vincent Cohen-Addad, Claire Mathieu, École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL), Laboratoire d'informatique de l'école normale supérieure (LIENS), Département d'informatique - ENS Paris (DI-ENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science (Brown University), Brown University, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Cohen-Addad, Vincent, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Discrete mathematics ,Clique-sum ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Vertex cover ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Bidimensionality ,Combinatorics ,Treewidth ,Indifference graph ,Pathwidth ,010201 computation theory & mathematics ,Chordal graph ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Maximal independent set ,ComputingMilieux_MISCELLANEOUS ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
We present a framework for addressing several problems on weighted planar graphs and graphs of bounded genus. With that framework, we derive polynomial-time approximation schemes for the following problems in planar graphs or graphs of bounded genus: edge-weighted tree cover and tour cover; vertex-weighted connected dominating set, max-weight-leaf spanning tree, and connected vertex cover. In addition, we obtain a polynomial-time approximation scheme for feedback vertex set in planar graphs. These are the first polynomial-time approximation schemes for all those problems in weighted embedded graphs. (For unweighted versions of some of these problems, polynomial-time approximation schemes were previously given using bidimensionality.)
- Published
- 2016
- Full Text
- View/download PDF