The convex-hull-and-line traveling salesman problem: a solvable case

@article{convexhulltsp-ipl51,
   abstract = {We solve the special case of the Euclidean Traveling Salesman Problem where n − m cities lie on the boundary of the convex hull of all n cities, and the other m cities lie on a line segment inside this convex hull by an algorithm which needs O(mn) time and O(n) space.},
   apice = {ConvexhulltspIpl51},
   author = {Vladimir G. Deineko and René van Dal and Günter Rote},
   doi = {10.1016/0020-0190(94)00071-9},
   issn = {0020-0190},
   journal = {Information Processing Letters},
   keywords = {Euclidean Traveling Salesman Problem, Shortest path, Well-solvable case, Polynomial time algorithm},
   month = aug,
   number = 3,
   numpages = 8,
   openalex = {W2003687734},
   pages = {141--148},
   publisher = {Elsevier B.V.},
   title = {The convex-hull-and-line traveling salesman problem: a solvable case},
   url = {https://www.sciencedirect.com/science/article/pii/0020019094000719},
   volume = 51,
   year = 1994
}