ISSN:
1432-0541
Schlagwort(e):
Steiner problem
;
Undirected graphs
;
Heuristics
;
Complexity
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01758765
Permalink
