AbstractTwo applications of sparsification to parametric computing are given. The first is a fast algorithm for enumerating all distinct minimum spanning trees in a graph whose edge weights vary linearly with a parameter. The second is an asymptotically optimal algorithm for the minimum ratio spanning tree problem, as well as other search problems, on dense graphs.
Categories and Subject Descriptors:
Additional Key Words and Phrases: algorithms, graphs, minimum ratio optimization, minimum spanning trees, parametric problems, sparsification
Selected papers that cite this one
- David Eppstein, Zvi Galil, and Amnon Nissenzweig. Sparsification -- a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5):669-696, September 1997.
Selected references
- Richard Cole. Slowing down sorting networks to obtain faster sorting algorithms. Journal of the ACM, 34(1):200-208, January 1987.
- Mark J. Eisner and Dennis G. Severance. Mathematical techniques for efficient record segmentation in large shared databases. Journal of the ACM, 23(4):619-635, October 1976.
- David Eppstein. Geometric lower bounds for parametric matroid optimization. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 662-671, Las Vegas, Nevada, 29 May-1 June 1995.
- David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification -- a technique for speeding up dynamic graph algorithms (extended abstract). In 33rd Annual Symposium on Foundations of Computer Science, pages 60-69, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing, 16(6):1004-1022, December 1987.
- Greg N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In 32nd Annual Symposium on Foundations of Computer Science, pages 632-641, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In 31st Annual Symposium on Foundations of Computer Science, volume II, pages 719-725, St. Louis, Missouri, 22-24 October 1990. IEEE.
- Dan Gusfield. Parametric combinatorial computing and a problem of program module distribution. Journal of the ACM, 30(3):551-563, July 1983.
- David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2):321-328, March 1995.
- Ji\v{r}í Matou\v{s}ek and Otfried Schwarzkopf. A deterministic algorithm for the three-dimensional diameter problem. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 478-484, San Diego, California, 16-18 May 1993.
- Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, October 1983.
- Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, June 1983.