Vi visar att varje H-minorfri graf har ett ljus (1 + )-spanner, löser ett öppet problem med Grigni och Sissokho [13] och bevisar en gissning om Grigni och Hung [12]. Vår ljushet som är bunden är O σH 3 log 1 där σH =  och V (H) och log  och V (H) är gleshetskoefficienten för H-minorfria grafer. Det vill säga, det har ett praktiskt beroende av storleken på den mindre H. Vårt resultat innebär också att polynom tid approximation systemet (PTAS) för Travelling Salesperson Problem (TSP) i H-minor-free grafer av Demaine, Hajiaghayi och Kawarabayashi [7] är en effektiv PTAS vars körtid är 2 O H 1 4 log 1 n O(1) där OH ignorerar beroenden av storleken på H. Våra tekniker avviker avsevärt från befintliga forskningslinjer på spannare för H-minor-fria grafer, men bygger vidare på arbetet av Chechik och Wulff-Nilsen för spannare av allmänna grafer [6].
Faktum är att sparsamhet används upprepade gånger i analysen av ljus skiftnycklar för H-minorfria grafer REF.
Minor-Free Graphs Have Light Spanners
{'venue': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}