• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Zhang, Hao (Zhang, Hao.) [1] (Scholars:张浩) | Ye, Dong-Yi (Ye, Dong-Yi.) [2] (Scholars:叶东毅) | Guo, Wen-Zhong (Guo, Wen-Zhong.) [3] (Scholars:郭文忠)

Indexed by:

EI Scopus

Abstract:

The underlying models of many practical problems in various engineering fields are equivalent to the Steiner tree problem in graphs, which is a typical NP-hard combinatorial optimization problem. Thus, developing a fast and effective heuristic for the Steiner tree problem in graphs is of universal significance. By analyzing the advantages and disadvantages of the fast classic heuristics, we find that the shortest paths and Steiner points play important roles in solving the Steiner tree problem in graphs. Based on the analyses, we propose a Steiner point candidate-based heuristic algorithm framework (SPCF) for solving the Steiner tree problem in graphs. SPCF consists of four stages: marking SPCI points, constructing the Steiner tree, eliminating the detour paths, and SPCII-based refining stage. For each procedure of SPCF, we present several alternative strategies to make the trade-off between the effectiveness and efficiency of the algorithm. By finding the shortest path clusters between vertex sets, several methods are proposed to mark the first type of Steiner point candidates SPCI. The solution qualities of the classic heuristics are effectively improved by looking SPCI points as terminals. By constructing a Voronoi diagram, a series of methods are suggested to mark the second type of Steiner point candidates SPCII. The feasible solution quality is efficiently improved by employing the SPCII points as the insertable key-vertices in key-vertex insertion local search method. Numerical experiments show that the proposed strategies are all effective for improving the solution quality. Compared with other effective algorithms, the proposed algorithms can achieve better solution quality and speed performance. © The Author(s) 2016.

Keyword:

Combinatorial optimization Computational geometry Economic and social effects Graphic methods Graph theory Heuristic algorithms

Community:

  • [ 1 ] [Zhang, Hao]Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, No. 2 Xueyuan Road, District of Universities, FuZhou; 350108, China
  • [ 2 ] [Zhang, Hao]College of Mathematics and Computer Science, Fuzhou University, FuZhou, China
  • [ 3 ] [Ye, Dong-Yi]Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, No. 2 Xueyuan Road, District of Universities, FuZhou; 350108, China
  • [ 4 ] [Ye, Dong-Yi]College of Mathematics and Computer Science, Fuzhou University, FuZhou, China
  • [ 5 ] [Guo, Wen-Zhong]College of Mathematics and Computer Science, Fuzhou University, FuZhou, China

Reprint 's Address:

  • 张浩

    [zhang, hao]center for discrete mathematics and theoretical computer science, fuzhou university, no. 2 xueyuan road, district of universities, fuzhou; 350108, china;;[zhang, hao]college of mathematics and computer science, fuzhou university, fuzhou, china

Show more details

Version:

Related Keywords:

Related Article:

Source :

Journal of Algorithms and Computational Technology

ISSN: 1748-3018

Year: 2016

Issue: 2

Volume: 10

Page: 99-114

0 . 8 0 0

JCR@2023

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:137/10042992
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1