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