Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
minor closed graph classes; minimum spanning trees
minor closed graph classes; minimum spanning trees
Summary:
This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in $O(\vert V\vert +\vert E\vert )$ time for any non-trivial class of graphs closed on graph minors. This applies in particular to planar graphs and graphs of bounded genus. Both algorithms run on a pointer machine and they require no a priori knowledge of the structure of the class except for its density. Edge weights are only compared.
References:
[1] Borůvka O.: O jistém problému minimálním (About a Certain Minimal Problem). Práce mor. přírodověd. spol. v Brně, III, (1926), 37–58. Czech with German summary.
[2] Frederickson G. N.: Data structures for on-line updating of minimum spanning trees. SIAM J. Comput. 14 (1985), 781–798. MR 0807881 | Zbl 0575.68068
[3] Fredman M., Willard D. E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. In Proceedings of FOCS’90 (1990), 719–725.
[4] Graham R. L., Hell P.: On the history of the minimum spanning tree problem. Ann. Hist. Comput. 7 (1985), 43–57. MR 0783327 | Zbl 0998.68003
[5] Chazelle B.: A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. J. ACM 47 (2000), 1028–1047. MR 1866456 | Zbl 1094.68606
[6] Karger D. R., Klein P. N., Tarjan R. E.: Linear expected-time algorithms for connectivity problems. J. ACM 42 (1995), 321–328. MR 1409738
[7] Matsui T.: The Minimum Spanning tree Problem on a Planar Graph. Discrete Appl. Math. 58 (1995), 91–94. MR 1323024 | Zbl 0823.05024
[8] Nešetřil J.: Some remarks on the history of MST-problem. Arch. Math. (Brno) 33 (1997), 15–22. MR 1464297
[9] Nešetřil J., de Mendez P. O.: Colorings and Homomorphism of Minor Closed Classes. To appear in Pollack-Goodman Festschrift, Springer Verlag, 2002. MR 2038495 | Zbl 1071.05526
[10] Nešetřil J., Milková E., Nešetřilová H.: Otakar Borůvka on Minimum Spanning Tree Problem. Discrete Math. 233(1–3) (2001), 3–36. Zbl 0999.01019
[11] Pettie S.: Finding minimum spanning trees in $O(m\alpha (m,n))$ time. Tech Report TR99-23, Univ. of Texas at Austin, 1999.
[12] Pettie S., Ramachandran V.: An Optimal Minimum Spanning Tree Algorithm. In Proceedings of ICALP’2000, 49–60, Springer Verlag, 2000. MR 1795885 | Zbl 0973.68534
[13] Tarjan R. E.: Data structures and network algorithms. 44 CMBS-NSF Regional Conf. Series in Appl. Math. SIAM, 1983. MR 0826534 | Zbl 0584.68077
Search
Partner of
