The Convex-hull-and-k-line travelling salesman problem

作     者：Deineko, VG Woeginger, GJ 

作者机构：EINDHOVEN UNIV TECHNOLDEPT MATH & COMP SCINL-5600 MB EINDHOVENNETHERLANDS GRAZ TECH UNIVINST MATH BA-8010 GRAZAUSTRIA 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1996年第59卷第6期

页      面：295-301页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Projektbereich Diskrete Optimierung Spezialforschungs-bereich F 003 

主　　题：travelling salesman problem polynomial algorithm combinatorial problems combinatorial optimization 

摘      要：We present a polynomial time solution algorithm for the so-called Convex-hull-and-k-line TSP: This is a special case of the Euclidean TSP where n - m of the cities lie on the convex hull and m of the cities lie on k almost parallel line segments in the interior of the hull such that the carrying lines of all these segments intersect the hull in two common edges. Our result contains and generalizes three earlier results that are due to Cutler (1980),to Rote (1992), and to Deineko, Van Dal and Rote (1994).