Deineko, Vladimir G., Klinz, Bettina, Tiskin, Alexander and Woeginger, Gerhard J. (2014) Four-point conditions for the TSP : the complete complexity classification. Discrete Optimization, Volume 14 . pp. 147-159. doi:10.1016/j.disopt.2014.09.003 ISSN 1572-5286.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

The combinatorial optimization literature contains a multitude of polynomially solvable special cases of the traveling salesman problem (TSP) which result from imposing certain combinatorial restrictions on the underlying distance matrices. Many of these special cases have the form of so-called four-point conditions: inequalities that involve the distances between four arbitrary cities.

In this paper we classify all possible four-point conditions for the TSP with respect to computational complexity, and we determine for each of them whether the resulting special case of the TSP can be solved in polynomial time or whether it remains NP-hard.

Item Type:	Journal Article
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Social Sciences > Warwick Business School
Journal or Publication Title:	Discrete Optimization
Publisher:	Elsevier Science BV
ISSN:	1572-5286
Official Date:	November 2014
Dates:	Date Event November 2014 Published 4 October 2014 Available 12 September 2014 Accepted 14 November 2014 Submitted
Volume:	Volume 14
Page Range:	pp. 147-159
DOI:	10.1016/j.disopt.2014.09.003
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access

Request changes or add full text files to a record

Repository staff actions (login required)

View Item