Linear-time algorithms for parametric minimum spanning tree problems on planar graphs. (English) Zbl 0901.68146
Summary: A linear-time algorithm for the minimum-ratio spanning tree problem on planar graphs is presented. The algorithm is based on a new planar minimum spanning tree algorithm. The approach extends to other parametric minimum spanning tree problems on planar graphs and to other families of graphs having small separators.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms, and Applications (1992), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [2] | Agarwala, R.; Fernández-Baca, D., Weighted multidimensional search and its application to convex optimization, SIAM J. Comput., 25, 83-99 (1996) · Zbl 0848.68026 |
| [3] | Ajtai, M.; Komlos, J.; Szemerédi, E., Sorting in \(c\) log n parallel steps, Combinatorica, 3, 1-19 (1983) · Zbl 0523.68048 |
| [4] | Batcher, K. E., Sorting networks and their applications, (Proc. AFIPS Spring Joint Summer Computer Conf., Vol. 32 (1968)), 307-314 · Zbl 0142.12903 |
| [5] | Camerini, P. M.; Maffioli, F.; Vercellis, C., Multi-constrained matroidal knapsack problems, Math. Programming, 45, 211-231 (1989) · Zbl 0682.90074 |
| [6] | Chandrasekaran, R., Minimal ratio spanning trees, Networks, 7, 335-342 (1977) · Zbl 0366.94044 |
| [7] | Chazelle, B.; Edelsbrunner, H.; Guibas, L.; Sharir, M., Diameter, width, closest line pair, and parametric searching, (Proc. 8th Ann. ACM Symp. on Computational Geometry (1992)), 120-129 |
| [8] | Cheriton, D.; Tarjan, R. E., Finding minimum spanning trees, SIAM J. Comput., 5, 724-742 (1976) · Zbl 0358.90069 |
| [9] | Cohen, E.; Megiddo, N., Maximizing concave functions in fixed dimension, (Pardalos, P. M., Complexity in Numerical Computations (1993), World Scientific Press: World Scientific Press Singapore), 74-87 · Zbl 0968.90504 |
| [10] | Cole, R., Slowing down sorting networks to obtain faster sorting algorithms, J. Assoc. Comput. Mach., 34, 200-208 (1987) · Zbl 1378.68037 |
| [11] | Cole, R.; Salowe, J. S.; Steiger, W. L.; Szemerédi, E., An optimal-time algorithm for slope selection, SIAM J. Comput., 18, 792-810 (1989) · Zbl 0678.68033 |
| [12] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge, MA · Zbl 1158.68538 |
| [13] | Fernández-Baca, D.; Slutzki, G., Optimal parametric search on graphs of bounded tree-width, J. Algorithms, 22, 212-240 (1997) · Zbl 0866.68029 |
| [14] | Fernández-Baca, D.; Williams, M. A., On matroids and hierarchical graphs, Inform. Processing Lett., 38, 117-121 (1991) · Zbl 0739.68070 |
| [15] | Frederickson, G. N., Fast algorithms for shortest paths in planar graphs, with applications, SIAM J. Comput., 16, 1004-1022 (1985) · Zbl 0654.68087 |
| [16] | Frederickson, G. N., Optimal algorithms for partitioning trees and locating \(p\)-centers in trees, (Tech. Report CSD-TR 1029 (October 1990), Department of Computer Science, Purdue University) · Zbl 0846.68025 |
| [17] | Fredman, M.; Willard, D., Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and Systems Sciences, 48, 533-551 (1994) · Zbl 0806.68057 |
| [18] | Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E., Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, 6, 109-122 (1986) · Zbl 0608.05027 |
| [19] | Gabow, H. N.; Tarjan, R. E., Efficient algorithms for a family of matroid intersection problems, J. Algorithms, 5, 80-131 (1984) · Zbl 0545.05029 |
| [20] | Gabow, H. N.; Tarjan, R. E., A linear-time algorithm for finding a minimum spanning pseudoforest, Inform. Processing Lett., 27, 259-263 (1988) · Zbl 0637.68045 |
| [21] | Goodrich, M. T., Planar separators and parallel polygon triangulation, (Proc. 24th Ann. Symp. on Theory of Computing (1992)), 507-516, Manuscript, A preliminary version appeared in |
| [22] | Gusfield, D., Parametric combinatorial computing and a problem in program module allocation, J. Assoc. Comput. Mach., 30, 551-563 (1983) · Zbl 0628.68035 |
| [23] | Karger, D. R.; Klein, P. N.; Tarjan, R. E., A randomized linear-time algorithm for finding minimum spanning trees, J. Assoc. Comput. Mach., 42, 2, 321-328 (1995), a preliminary version appeared in STOC 94. · Zbl 0886.68079 |
| [24] | Klein; Rao, S.; Rauch, M.; Subramanian, S., Faster shortest-path algorithms for planar graphs, (Proc. 26th Annual ACM Symposium on Theory of Computing (1994)), 27-37 · Zbl 1345.05103 |
| [25] | Kruskal, J. B., On the shortest spanning tree of a graph and the traveling salesman problem, (Proc. Amer. Math. Soc., 7 (1956)), 48-50 · Zbl 0070.18404 |
| [26] | Lengauer, T., Efficient algorithms for finding minimum spanning forests in hierarchically defined graphs, J. Algorithms, 8, 260-284 (1987) · Zbl 0633.68023 |
| [27] | Lipton, R. J.; Tarjan, R. E., A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177-189 (1979) · Zbl 0432.05022 |
| [28] | Matous̆ek, J.; Schwartzkopf, O., A deterministic algorithm for the three-dimensional diameter problem, (Proc. 25th Ann. Symp. on Theory of Computing (1993)), 478-484 · Zbl 1310.68208 |
| [29] | Matthews, L. R., Infinite subgraphs as matroid circuits, J. Combin. Theory Ser. B, 27, 260-273 (1979) · Zbl 0433.05018 |
| [30] | Megiddo, N., Combinatorial optimization with rational objective functions, Math. Oper. Res., 4, 414-424 (1979) · Zbl 0425.90076 |
| [31] | Megiddo, N., Applying parallel computation algorithms in the design of serial algorithms, J. Assoc. Comput. Mach., 30, 852-865 (1983) · Zbl 0627.68034 |
| [32] | Tarjan, R. E., Data Structures and Network Algorithms (1983), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 0584.68077 |
| [33] | Toledo, S., Maximizing non-linear convex functions in fixed dimension, (Pardalos, P. M., Complexity in Numerical Computations (1993), World Scientific Press: World Scientific Press Singapore), 74-87, A preliminary version appeared in FOCS 92. · Zbl 0968.90504 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
