Light spanners for bounded treewidth graphs imply light spanners for $H$-minor-free graphs

March 30, 2017 Β· Declared Dead Β· πŸ› arXiv.org

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Glencora Borradaile, Hung Le arXiv ID 1703.10633 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM Citations 1 Venue arXiv.org Last Checked 4 months ago
Abstract
Grigni and Hung~\cite{GH12} conjectured that H-minor-free graphs have $(1+Ξ΅)$-spanners that are light, that is, of weight $g(|H|,Ξ΅)$ times the weight of the minimum spanning tree for some function $g$. This conjecture implies the {\em efficient} polynomial-time approximation scheme (PTAS) of the traveling salesperson problem in $H$-minor free graphs; that is, a PTAS whose running time is of the form $2^{f(Ξ΅)}n^{O(1)}$ for some function $f$. The state of the art PTAS for TSP in H-minor-free-graphs has running time $n^{1/Ξ΅^c}$. We take a further step toward proving this conjecture by showing that if the bounded treewidth graphs have light greedy spanners, then the conjecture is true. We also prove that the greedy spanner of a bounded pathwidth graph is light and discuss the possibility of extending our proof to bounded treewidth graphs.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted