سال انتشار: ۱۳۹۰
محل انتشار: اولین کنفرانس ملی دانش پژوهان کامپیوتر و فناوری اطلاعات
تعداد صفحات: ۶
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. Thelgorithm 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.