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.
