سال انتشار: ۱۳۹۰

محل انتشار: اولین کنفرانس ملی دانش پژوهان کامپیوتر و فناوری اطلاعات

تعداد صفحات: ۵

نویسنده(ها):

ali Nourollah – Department of Electrical and Computer Engineering of Shahid Rajaee Teacher Training University
elnaz pashaei – Department of Electrical, Computer and IT Engineering, Qazvin Islamic Azad University
elham pashaei – Department of Electrical, Computer and IT Engineering, Qazvin Islamic Azad University
mohammad reza meybodi – Department of IT & Computer Engineering, Amirkabir University of Technology,

چکیده:

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum weight subtree spanning a given subset of (terminal) nodes of the original graph, which it is NP-complete. In this paper, we first review one of the existing algorithms for solving the Steiner problem in graphs, Shortest Path Heuristic algorithm, then presenting a new heuristic algorithm ISPH to improve it. We describe our algorithm and its computational results. It is shown that our algorithm can effectively improve the performance on SPH.