Geodesic
Two linear time algorithms for MST on minor closed graph classes
Archivum mathematicum, Tome 40 (2004) no. 3, pp. 315-320
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C05, 05C85, 68R10
Keywords: minor closed graph classes; minimum spanning trees 
@article{ARM_2004_40_3_a11,
     author = {Mare\v{s}, Martin},
     title = {Two linear time algorithms for {MST} on minor closed graph classes},
     journal = {Archivum mathematicum},
     pages = {315--320},
     year = {2004},
     volume = {40},
     number = {3},
     mrnumber = {2107027},
     zbl = {1116.05079},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ARM_2004_40_3_a11/}
}
TY  - JOUR
AU  - Mareš, Martin
TI  - Two linear time algorithms for MST on minor closed graph classes
JO  - Archivum mathematicum
PY  - 2004
SP  - 315
EP  - 320
VL  - 40
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/ARM_2004_40_3_a11/
LA  - en
ID  - ARM_2004_40_3_a11
ER  - 
%0 Journal Article
%A Mareš, Martin
%T Two linear time algorithms for MST on minor closed graph classes
%J Archivum mathematicum
%D 2004
%P 315-320
%V 40
%N 3
%U http://geodesic.mathdoc.fr/item/ARM_2004_40_3_a11/
%G en
%F ARM_2004_40_3_a11
Mareš, Martin. Two linear time algorithms for MST on minor closed graph classes. Archivum mathematicum, Tome 40 (2004) no. 3, pp. 315-320. http://geodesic.mathdoc.fr/item/ARM_2004_40_3_a11/

[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 | Zbl

[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 | Zbl

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

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

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

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

[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 | Zbl

[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

[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 | Zbl

[13] Tarjan R. E.: Data structures and network algorithms. 44 CMBS-NSF Regional Conf. Series in Appl. Math. SIAM, 1983. | MR | Zbl