A Linear Time Algorithm for the $3$-Neighbour Traveling Salesman Problem on Halin graphs and extensions.

摘要: The Quadratic Travelling Salesman Problem (QTSP) is to find a least cost Hamilton cycle in an edge-weighted graph, where costs are defined on all pairs of edges contained the cycle. This more general version than commonly studied QTSP which only considers adjacent edges. We define restricted QTSP, $k$-neighbour TSP (TSP($k$)), and give linear time algorithm solve TSP($k$) Halin graph for $k\leq 3$. can be extended any fully reducible class graphs fixed $k$ polynomial time. result generalizes corresponding results standard TSP. used model various machine scheduling problems as well optimal routing problem unmanned aerial vehicles (UAVs).