A 4/3-approximation for TSP on cubic 3-edge-connected graphs

arxiv: 1101.5586 · v1 · pith:Q6MZTAY6new · submitted 2011-01-28 · 💻 cs.DS

Nishita Aggarwal , Naveen Garg , Swati Gupta This is my paper

classification 💻 cs.DS

keywords approximationcubicgraphsalgorithmarisingcompletionconnectededge

0 comments

read the original abstract

We provide a polynomial time 4/3 approximation algorithm for TSP on metrics arising from the metric completion of cubic 3-edge connected graphs.

This paper has not been read by Pith yet.