# Two linear time algorithms for MST on minor closed graph classes

Archivum Mathematicum (2004)

- Volume: 040, Issue: 3, page 315-320
- ISSN: 0044-8753

## Access Full Article

top## Abstract

top## How to cite

topMareš, Martin. "Two linear time algorithms for MST on minor closed graph classes." Archivum Mathematicum 040.3 (2004): 315-320. <http://eudml.org/doc/249321>.

@article{Mareš2004,

abstract = {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.},

author = {Mareš, Martin},

journal = {Archivum Mathematicum},

keywords = {minor closed graph classes; minimum spanning trees; minimum spanning tree; deterministic algorithms},

language = {eng},

number = {3},

pages = {315-320},

publisher = {Department of Mathematics, Faculty of Science of Masaryk University, Brno},

title = {Two linear time algorithms for MST on minor closed graph classes},

url = {http://eudml.org/doc/249321},

volume = {040},

year = {2004},

}

TY - JOUR

AU - Mareš, Martin

TI - Two linear time algorithms for MST on minor closed graph classes

JO - Archivum Mathematicum

PY - 2004

PB - Department of Mathematics, Faculty of Science of Masaryk University, Brno

VL - 040

IS - 3

SP - 315

EP - 320

AB - 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.

LA - eng

KW - minor closed graph classes; minimum spanning trees; minimum spanning tree; deterministic algorithms

UR - http://eudml.org/doc/249321

ER -

## References

top- 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) Zbl0575.68068MR0807881
- 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) Zbl0998.68003MR0783327
- Chazelle B., A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, J. ACM 47 (2000), 1028–1047. Zbl1094.68606MR1866456
- Karger D. R., Klein P. N., Tarjan R. E., Linear expected-time algorithms for connectivity problems, J. ACM 42 (1995), 321–328. (1995) MR1409738
- Matsui T., The Minimum Spanning tree Problem on a Planar Graph, Discrete Appl. Math. 58 (1995), 91–94. (1995) Zbl0823.05024MR1323024
- Nešetřil J., Some remarks on the history of MST-problem, Arch. Math. (Brno) 33 (1997), 15–22. (1997) MR1464297
- Nešetřil J., de Mendez P. O., Colorings and Homomorphism of Minor Closed Classes, To appear in Pollack-Goodman Festschrift, Springer Verlag, 2002. Zbl1071.05526MR2038495
- 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. Zbl0999.01019
- Pettie S., Finding minimum spanning trees in $O\left(m\alpha \right(m,n\left)\right)$ 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. Zbl0973.68534MR1795885
- Tarjan R. E., Data structures and network algorithms, 44 CMBS-NSF Regional Conf. Series in Appl. Math. SIAM, 1983. (1983) Zbl0584.68077MR0826534

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.