An O(n log n) average time algorithm for computing the shortest network under a given topology

An O(n log n) average time algorithm for computing the shortest network under a given topology

0.00 Avg rating0 Votes
Article ID: iaor20011493
Country: United States
Volume: 23
Issue: 4
Start Page Number: 354
End Page Number: 362
Publication Date: Apr 1999
Journal: Algorithmica
Authors: ,
Keywords: graphs
Abstract:

In 1992 F.K. Hwang and J.F. Weng published an O(n2) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang–Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang–Weng algorithm. While the worst-case time complexity of our algorithm is still O(n2), its average time complexity over all the full Steiner topologies interconnecting n fixed points is O(n log n).

Reviews

Required fields are marked *. Your email address will not be published.