|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-Reports 2013 | Copyright 2013 University of Bonn, Department of Computer Science, Abt. V | |
|
85338 25.04.2013 |
Approximation Hardness of Graphic TSP on Cubic Graphs
Marek Karpinski and Richard Schmied [Download PostScript] [Download PDF] We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used in the paper could be also of independent interest. |
|
|
Last Change:
11/05/14 at 11:03:51
|
University of Bonn -> Department of Computer Science -> Chair V | |