Nordic Journal of Computing Bibliography

Joseph L. Ganley and Jeffrey S. Salowe. The Power-p Steiner Tree Problem. Nordic Journal of Computing, 5(2):115-127, Summer 1998.

This paper introduces the power-p Steiner tree problem, which is to find a geometric Steiner tree that minimizes the sum of the edge lengths each raised to the p power. A number of results are presented on computing optimal and approximate power-p Steiner trees. Specifically, a linear-time numerical algorithm is presented for computing optimal Euclidean power-2 Steiner trees with respect to a given topology, and the algorithm is proved to be numerically stable. It is conjectured, and strong evidence given, that the power-p Steiner tree problem is not finitely solvable for p >= 5. Finally, bounds are given on the power-p Steiner ratio, which measures the quality of a minimum spanning tree as an approximation of an optimal power-p Steiner tree.

Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; G.1 [Numerical Analysis]; G.2 [Discrete Mathematics]

Additional Key Words and Phrases: Steiner tree, geometric algorithms, approximation, facility location

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database