Two linear time algorithms for MST on minor closed graph classes
Mareš, Martin
Archivum Mathematicum, Tome 040 (2004), p. 315-320 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2004-01-01
Classification:  05C05,  05C85,  68R10 
@article{107914,
     author = {Martin Mare\v s},
     title = {Two linear time algorithms for MST on minor closed graph classes},
     journal = {Archivum Mathematicum},
     volume = {040},
     year = {2004},
     pages = {315-320},
     zbl = {1116.05079},
     mrnumber = {2107027},
     language = {en},
     url = {http://dml.mathdoc.fr/item/107914}
}

Mareš, Martin. Two linear time algorithms for MST on minor closed graph classes. Archivum Mathematicum, Tome 040 (2004) pp. 315-320. http://gdmltest.u-ga.fr/item/107914/

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. (1926)

Frederickson G. N. Data structures for on-line updating of minimum spanning trees, SIAM J. Comput. 14 (1985), 781–798. (1985) | MR 0807881 | Zbl 0575.68068

Fredman M.; Willard D. E. Trans-dichotomous algorithms for minimum spanning trees and shortest paths, In Proceedings of FOCS’90 (1990), 719–725. (1990)

Graham R. L.; Hell P. On the history of the minimum spanning tree problem, Ann. Hist. Comput. 7 (1985), 43–57. (1985) | MR 0783327 | Zbl 0998.68003

Chazelle B. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, J. ACM 47 (2000), 1028–1047. | MR 1866456 | Zbl 1094.68606

Karger D. R.; Klein P. N.; Tarjan R. E. Linear expected-time algorithms for connectivity problems, J. ACM 42 (1995), 321–328. (1995) | MR 1409738

Matsui T. The Minimum Spanning tree Problem on a Planar Graph, Discrete Appl. Math. 58 (1995), 91–94. (1995) | MR 1323024 | Zbl 0823.05024

Nešetřil J. Some remarks on the history of MST-problem, Arch. Math. (Brno) 33 (1997), 15–22. (1997) | MR 1464297

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

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

Pettie S. Finding minimum spanning trees in $O(m\alpha (m,n))$ time, Tech Report TR99-23, Univ. of Texas at Austin, 1999. (1999)

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

Tarjan R. E. Data structures and network algorithms, 44 CMBS-NSF Regional Conf. Series in Appl. Math. SIAM, 1983. (1983) | MR 0826534 | Zbl 0584.68077