Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs

作者: Erik D. Demaine , MohammadTaghi Hajiaghayi , Ken-ichi Kawarabayashi

DOI: 10.1007/978-3-642-02927-1_27

关键词:

摘要: We develop new structural results for apex-minor-free graphs and show their power by developing two approximation algorithms. The first is an additive coloring within 2 of the optimal chromatic number, which essentially best possible, generalizes seminal result Thomassen [32] bounded-genus graphs. This also improves our understanding from algorithmic point view venerable Hadwiger conjecture about H -minor-free second a PTAS unweighted TSP in graphs, PTASs planar [20,2,24,15]. We strengthen Graph Minor Theory Robertson Seymour case showing that apices can be made adjacent only to vortices if we generalize notion "quasivortices" bounded treewidth, proving [10]. this structure theorem powerful tool algorithms on including classic problems TSP. In particular, use partition edges graph into k pieces, any , such contracting piece bounded-treewidth graph, generalizing previous similar [24] [15]. highlight difficulties extending general

参考文章(35)
Carsten Thomassen, Bojan Mohar, Graphs on Surfaces ,(2001)
Michelangelo Grigni, Approximate TSP in Graphs with Forbidden Minors international colloquium on automata languages and programming. pp. 869- 877 ,(2000) , 10.1007/3-540-45022-X_73
Avrim Blum, David Karger, An Õ( n 3/14 )-coloring algorithm for 3-colorable graphs Information Processing Letters. ,vol. 61, pp. 49- 53 ,(1997) , 10.1016/S0020-0190(96)00190-1
André Berger, Artur Czumaj, Michelangelo Grigni, Hairong Zhao, Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs Algorithms – ESA 2005. ,vol. 3669, pp. 472- 483 ,(2005) , 10.1007/11561071_43
Ken-ichi Kawarabayashi, Bojan Mohar, List-color-critical graphs on a fixed surface symposium on discrete algorithms. pp. 1156- 1165 ,(2009) , 10.5555/1496770.1496895
Matthew Hennessy, Robin Milner, On Observing Nondeterminism and Concurrency international colloquium on automata, languages and programming. pp. 299- 309 ,(1980) , 10.1007/3-540-10003-2_79
Michelangelo Grigni, Artur Czumaj, Papa Sissokho, Hairong Zhao, Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs symposium on discrete algorithms. pp. 496- 505 ,(2004) , 10.5555/982792.982863
Carsten Thomassen, The chromatic number of a graph of girth 5 on a fixed surface Journal of Combinatorial Theory, Series B. ,vol. 87, pp. 38- 71 ,(2003) , 10.1016/S0095-8956(02)00027-8
C. Thomassen, Five-Coloring Maps on Surfaces Journal of Combinatorial Theory, Series B. ,vol. 59, pp. 89- 105 ,(1993) , 10.1006/JCTB.1993.1057
Carsten Thomassen, Color-Critical Graphs on a Fixed Surface Journal of Combinatorial Theory, Series B. ,vol. 70, pp. 67- 100 ,(1997) , 10.1006/JCTB.1996.1722