On the steiner walk problem. (c2009)

Abstract

Given a Euclidean graph G = (Y, E) with a special set of vertices, called the terminal s, the Euclidean Steiner Walk problem asks for a walk through the vertices of the graph that starts and ends at a particular point, called the center, such that every terminal vertex is visited and the total cost of the walk (or distance) is minimized. Despite its wealth of real applications, Euclidean Steiner Walk (ESW) seems to have been neglected thus far by the computing community. We show, easily, that the problem is NP-Complete and present a suite of heuristic approaches for computing efficient approximate solutions to the problem. A Graphical User Interface is also provided for users of our software and to allow developers to conduct further experimental work on the problem.