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
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;
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
DOI :
10.1109/CISE.2010.5677025
