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

Hadrien Cambazard, Nicolas Catusse

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 re…