Skip navigation
Skip navigation

The backbone of the travelling salesperson

Kilby, Philip; Slaney, John K; Walsh, Toby


We study the backbone of the travelling salesperson optimization problem. We prove that it is intractable to approximate the backbone with any performance guarantee, assuming that P≠NP and there is a limit on the number of edges falsely returned. Nevert

CollectionsANU Research Publications
Date published: 2005
Type: Conference paper
Source: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005)


File Description SizeFormat Image
01_Kilby_The_backbone_of_the_travelling_2005.pdf1.03 MBAdobe PDF    Request a copy
02_Kilby_The_backbone_of_the_travelling_2005.pdf238.8 kBAdobe PDF    Request a copy
03_Kilby_The_backbone_of_the_travelling_2005.pdf1.4 MBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator