Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-023 | 12th February 2003 00:00

On Spanning Cacti and Asymmetric TSP

RSS-Feed




TR03-023
Authors: Anna Palbom
Publication: 15th April 2003 19:38
Downloads: 3325
Keywords: 


Abstract:

In an attempt to generalize Christofides algorithm for metric TSP to the asymmetric TSP with triangle inequality we have studied various properties of directed spanning cacti. In this paper we first observe that finding the TSP in a directed, weighted complete graph with triangle inequality is polynomial time equivalent to finding the minimum spanning cactus in the graph and then prove that it is NP-complete to determine whether a general unweighted digraph contains a directed spanning cactus. The proof is a reduction from Exact cover and may be of independent interest.



ISSN 1433-8092 | Imprint