Transitions in geometric minimum spanning trees

T. Asano, B. Bhattacharya, M. Keil, and F. F. Yao. Clustering algorithms based on minimum and maximum spanning trees.Proceedings of the 4th Annual Symposium on Computational Geometry, 1988, pp. 252–257.

M. J. Atallah. Some dynamic computational geometry problems.Journal of Computational and Applied Mathematics, Vol. 11, 1985, pp. 1117–1181.

B. Chazelle, R. Cole, F. P. Preparata, and C. Yap. New upper bounds for neighbor searching.Information and Control, Vol. 68, 1986, pp. 105–124.

L. P. Chew and R. L. Drysdale. Voronoi diagrams based on convex distance functions.Proceedings of the 1st ACM Symposium on Computational Geometry, 1985, pp. 235–244.

W. Cunningham. Optimal attack and reinforcement of a network.Journal of the Association for Computing Machinery, Vol. 32, No. 3, 1985, pp. 549–561.

M. E. Dyer. On a multidimensional search technique and its application to the Euclidean one-center problem.SIAM Journal on Computing, Vol. 15, 1986, pp. 725–738.

H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, 1987.

G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm.SIAM Journal on Computing, Vol. 18, 1989, pp. 30–55.

G. Georgakopoulos and C. H. Papadimitriou. The 1-Steiner tree problem.Journal of Algorithms, Vol. 8, 1987, pp. 122–130.

D. Gusfield. Bounds for the parametric spanning tree problem.Proceedings of the Humbolt Conference on Graph Theory, Combinatorics and Computing, 1979, pp. 173–183.

D. Gusfield. Sensitivity analysis for combinatorial optimization. Ph.D. thesis, University of California, Berkeley, 1980.

D. Gusfield. Parametric combinatorial optimization and a problem of program module distribution.Journal of the Association for Computing Machinery, Vol. 30, No. 3, 1983, pp. 551–563.

D. Gusfield and R. Irving. Parametric stable marriage and minimum cuts.Information Processing Letters, Vol. 30, 1989, pp. 255–259.

D. Gusfield and C. Martel. A fast algorithm for the generalized parametric minimum cut problem and applications. Technical Report CSE-89-21, University of California, Davis, 1989.

D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors.SIAM Journal on Computing, Vol. 13, No. 2, 1984, pp. 338–355.

C. Monma, M. Paterson, S. Suri, and F. Yao. Computing Euclidean maximum spanning trees.Algorithmica, Vol. 5, 1990, pp. 407–419.

J. C. Picard and M. Queyranne. Selected applications of minimum cuts in a network.INFOR—Canadian Journal of Operations Research and Information Processing, Vol. 20, 1982, pp. 394–422.

J. C. Picard and H. Ratliff. A cut approach to the rectilinear distance facility location problem.Operations Research, Vol. 26, 1978, pp. 422–433.

D. D. Sleater and R. E. Tarjan. A data structure for dynamic trees.Journal of Computer and Systems Sciences, Vol. 26, 1983, pp. 362–391.

A. C. C. Yao. On constructing minimum spanning trees ink-dimensional space and related problems.SIAM Journal on Computing, Vol. 11, No. 4, 1982, pp. 721–736.