Ali Nourollah - Department of Electrical and Computer Engineering of Shahid Rajaee Teacher Training University
elham pashaei - Department of Electrical, Computer and IT Engineering, Qazvin Islamic Azad University
Elnaz pashaei - Department of Electrical, Computer and IT Engineering, Qazvin Islamic Azad University
Alireza Bagheri - Department of Computer Engineering and Information Technology, Amirkabir University

Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present a novel heuristic for the Euclidean Steiner tree problem. The lgorithm utilizes the straight skeleton of simple polygon to generate candidate Steiner points, and a path heuristic to constructing Steiner minimum tree by using some of the candidate Steiner points in Euclidean plane. We present computational results on the Soukup test problems.

Euclidean Steiner Minimal Tree; straight skeleton of simple polygon; path heuristic