Minor-Free Graphs Have Light Spanners
Minor-Free Graphs Have Light Spanners
复制标题
无次要图有轻扳手
DOI：
10.1109/focs.2017.76
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Christian Wulff
中科院分区：
文献类型：
--
作者：
G. Borradaile;Hung Le;Christian Wulff
We show that every H-minor-free graph has a light (1+≥ilon)-spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung \cite{GH12}. Our lightness bound is \[O\left(\frac{\sigma_H}{≥ilon^3}\log \frac{1}{≥ilon}\right)\] where \sigma_H = |V(H)|√{\log |V(H)|} is the sparsity coefficient of H-minor-free graphs. That is, it has a practical dependency on the size of the minor H. Our result also implies that the polynomial time approximation scheme (PTAS) for the Travelling Salesperson Problem (TSP) in H-minor-free graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose running time is 2^{O_H\left(\frac{1}{≥ilon^4}\log \frac{1}{≥ilon}\right)}n^{O(1)} where O_H ignores dependencies on the size of H. Our techniques significantly deviate from existing lines of research on spanners for H-minor-free graphs, but build upon the work of Chechik and Wulff-Nilsen for spanners of general graphs[6].
We show that every H-minor-free graph has a light (1+≥ilon)-spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung \cite{GH12}. Our lightness bound is \[O\left(\frac{\sigma_H}{≥ilon^3}\log \frac{1}{≥ilon}\right)\] where \sigma_H = |V(H)|√{\log |V(H)|} is the sparsity coefficient of H-minor-free graphs. That is, it has a practical dependency on the size of the minor H. Our result also implies that the polynomial time approximation scheme (PTAS) for the Travelling Salesperson Problem (TSP) in H-minor-free graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose running time is 2^{O_H\left(\frac{1}{≥ilon^4}\log \frac{1}{≥ilon}\right)}n^{O(1)} where O_H ignores dependencies on the size of H. Our techniques significantly deviate from existing lines of research on spanners for H-minor-free graphs, but build upon the work of Chechik and Wulff-Nilsen for spanners of general graphs[6].