Name
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.)
|
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2897518.2897635 | STOC '16: Symposium on Theory of Computing
Cambridge
MA
USA
June, 2016 |
Keywords | Field | DocType |
Approximation algorithm,polynomial-time approximation scheme,graph,bounded genus,planar graph,connected dominating set,feedback vertex set | Discrete mathematics,Indifference graph,Combinatorics,Clique-sum,Chordal graph,Vertex cover,Treewidth,Pathwidth,Mathematics,Maximal independent set,Bidimensionality | Conference |
ISSN | ISBN | Citations |
0737-8017 | 978-1-4503-4132-5 | 3 |
PageRank | References | Authors |
0.37 | 30 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Cohen-Addad | 1 | 85 | 25.47 |
| Éric Colin de Verdière | 2 | 395 | 24.87 |
| Philip N. Klein | 3 | 2681 | 256.19 |
| Claire Mathieu | 4 | 6 | 2.78 |
| David Meierfrankenfeld | 5 | 3 | 1.05 |