Generalized travelling salesman problems on Halin graphs
Brad Woods · Summit (Simon Fraser University) · 2010
This thesis gives a complete survey of existing results on optimization problems on a Halin graph and some closely related graphs.Also presented are some new results on specific optimization problems.It is shown that the k-neighbor TSP and its bottleneck version are solvable in linear time on a Halin graph for k ≤ 2. These problems are special cases of the quadratic TSP and bottleneck quadratic TSP, both are shown to be strongly NP-complete on a Halin graph.For the k = 3 case, both versions are solved on some special cases.All these results are extended to directed Halin graphs.