ISSN:
1432-0541
Keywords:
Steiner problem
;
Undirected graphs
;
Heuristics
;
Complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract An integrative overview of the algorithmic characteristics of three well-known polynomialtime heuristics for the undirected Steiner minimum tree problem:shortest path heuristic (SPH),distance network heuristic (DNH), andaverage distance heuristic (ADH) is given. The performance of thesesingle-pass heuristics (and some variants) is compared and contrasted with several heuristics based onrepetitive applications of the SPH. It is shown that two of these repetitive SPH variants generate solutions that in general are better than solutions obtained by any single-pass heuristic. The worst-case time complexity of the two new variants isO(pn 3) andO(p 3 n 2), while the worst-case time complexity of the SPH, DNH, and ADH is respectivelyO(pn 2),O(m + n logn), andO(n 3) wherep is the number of vertices to be spanned,n is the total number of vertices, andm is the total number of edges. However, use of few simple tests is shown to provide large reductions of problem instances (both in terms of vertices and in term of edges). As a consequence, a substantial speed-up is obtained so that the repetitive variants are also competitive with respect to running times.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758765
Permalink
