Bounded diameter minimum spanning trees and related problems

ABSTRACT

We consider the problem of finding a minimum diameter spanning tree (MDST) of a set of n points in the Euclidean plane. The diameter of a spanning tree is the maximum distance between any two points in the tree. We give a characterization of an MDST and present a &thgr;(n3 time algorithm for solving the problem. We also show that for a weighted undirected graph, the problem of determining if a spanning tree with total weight and diameter upper bounded, respectively, by two given parameters C and D exists is N P-complete. The geometrical minimum diameter Steiner tree problem, in which new points are allowed to be part of the spanning tree, is shown to be solvable in &Ogr;(n) time.

REFERENCES

• 1: W. G. Brown. Reviews in Graph Theory. American Mathematical Society, Providence, RI, 1980.
• 2: D. Cheriton and R.E. Tarjan. Finding minimum spanning trees. SIAM J. Comput., 5(4):724-742, December 1976.
• 3: M. E. Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM J. Cornputing, 13:31-45, February 1984.
• 4: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: M. R. Garey and D. S. Johnson. Unpublished results. see {5, p.2061 for details.
• 7: I. G. Gowda, D. G. Kirkpatrick, D. T. Lee, and A. Naamad. Dynamic voronoi diagrams. IEEE Transaction on Information Theory, IT-29(5), September 1983.
• 8: D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12(1):28-35, February 1983.
• 9: D. T. Lee. Farthest neighbor Voronoi diagrams and applications. Technical Report Tech. Rep. #80-11-FC-04, Dept. Elec. Eng./Comput. Sci., Northwestern Univ., Evanston, IL, November 1980.
• 10: N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Computing, 12(4):759-776, November 1983.
• 11: F. P. Preparata. A new approach to planar point location. SIAM J. Comput., 10:473-482, August 1981.
• 12: R. C. Prim. Shortest connecting networks and some generalizations. BSTJ 96, 1389-1401, 1957.
• 13: M. I. Shamos and D. Hoey. Closest-point problems. In Sixteenth Annual IEEE Symposium on Foundations of Computer Science, pages 151- 162, October 1975.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory