Graphic TSP in cubic graphs

August 26, 2016 · The Ethereal · 🏛 Symposium on Theoretical Aspects of Computer Science

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Zdenek Dvorak, Daniel Kral, Bojan Mohar arXiv ID 1608.07568 Category cs.DM: Discrete Mathematics Cross-listed cs.DS, math.CO Citations 8 Venue Symposium on Theoretical Aspects of Computer Science Last Checked 2 months ago
Abstract
We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

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

📜 Similar Papers

In the same crypt — Discrete Mathematics