Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SPANNING CACTI:
Reports tagged with spanning cacti:
TR03-023 | 12th February 2003
Anna Palbom

On Spanning Cacti and Asymmetric TSP

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 ... more >>>




ISSN 1433-8092 | Imprint