# Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the plane

arXiv: https://arxiv.org/abs/1512.06649 · HTML: https://mlsanity.com/paper/1512.06649/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2015.

## Built on by (most cited first, 1 of 1)

- [Playing hide and seek: tackling in-store picking operations while improving customer experience](https://mlsanity.com/paper/2301.02142/) (2023)

## Abstract (arXiv)

Given a set P of n points with their pairwise distances, the traveling salesman problem (TSP) asks for a shortest tour that visits each point exactly once. A TSP instance is rectilinear when the points lie in the plane and the distance considered between two points is the l1 distance. In this paper, a fixed-parameter algorithm for the Rectilinear TSP is presented and relies on techniques for solving TSP on bounded-treewidth graphs. It proves that the problem can be solved in Oleft(nh7hright) where h ≤ n denotes the number of horizontal lines containing the points of P. The same technique can be directly applied to the problem of finding a shortest rectilinear Steiner tree that interconnects the points of P providing a Oleft(nh5hright) time complexity. Both bounds improve over the best time bounds known for these problems.