The Library
The traveling salesman problem with few inner points
Tools
UNSPECIFIED (2004) The traveling salesman problem with few inner points. In: 10th International Computing and Combinatories Conference (COCOON 2004), Jeju Isl, SOUTH KOREA, AUG 17-20, 2004. Published in: COMPUTING AND COMBINATORICS, PROCEEDINGS, 3106 pp. 268-277. ISBN 3-540-22856-X. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
We study the traveling salesman problem (TSP) in the 2-dimensional Euclidean plane. The problem is NP-hard in general, but trivial if the points are in convex position. In this paper, we investigate the influence of the number of inner points (i.e., points in the interior of the convex hull) on the computational complexity of the problem. We give two simple algorithms for this problem. The first one runs in 0(k!kn) time and O(k) space, and the second runs in 0(2(k)k(2)n) time and 0(2(k)kn) space, when n is the total number of input points and k is the number of inner points. Hence, if k is taken as a parameter, this problem is fixed-parameter tractable (FPT), and also can be solved in polynomial time if k = 0 (log n). We also consider variants of the TSP such as the prize-collecting TSP and the partial TSP in this setting, and show that they are FPT as well.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | COMPUTING AND COMBINATORICS, PROCEEDINGS | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-22856-X | ||||
ISSN: | 0302-9743 | ||||
Editor: | Chwa, KY and Munro, JI | ||||
Official Date: | 2004 | ||||
Dates: |
|
||||
Volume: | 3106 | ||||
Number of Pages: | 10 | ||||
Page Range: | pp. 268-277 | ||||
Publication Status: | Published | ||||
Title of Event: | 10th International Computing and Combinatories Conference (COCOON 2004) | ||||
Location of Event: | Jeju Isl, SOUTH KOREA | ||||
Date(s) of Event: | AUG 17-20, 2004 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |