DocumentCode :
1876771
Title :
A New Effective Heuristic for Solving Minimal Steiner Tree Problem on Graphs
Author :
Hu, Yan ; Jiang, He ; Qin, Zhenquan
Author_Institution :
Sch. of Software, Dalian Univ. of Technol., Dalian, China
fYear :
2010
fDate :
10-12 Dec. 2010
Firstpage :
1
Lastpage :
4
Abstract :
Minimal Steiner tree problem on graphs is a traditional optimization problem, which has wide- spread use in different application areas. Greedy heuristics for all the people to use the problem are using the shortest path heuristic, and various variants are also used. In this paper, a new heuristic for solving STPG is proposed. The new heuristic defined a novel neighborhood for local search methods. Experimental results show that the new heuristic outperforms the normal MPH heuristic in solution quality.
Keywords :
graph theory; graphs; greedy algorithms; optimisation; tree searching; graphs; greedy heuristics; local search method; optimization problem; shortest path heuristic; solving minimal Steiner tree problem; Algorithm design and analysis; Approximation algorithms; Approximation methods; Heuristic algorithms; Optimization; Routing; Steiner trees;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Intelligence and Software Engineering (CiSE), 2010 International Conference on
Conference_Location :
Wuhan
Print_ISBN :
978-1-4244-5391-7
Electronic_ISBN :
978-1-4244-5392-4
Type :
conf
DOI :
10.1109/CISE.2010.5677025
Filename :
5677025
Link To Document :
بازگشت