作者: 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