Two linear time algorithms for MST on minor closed graph classes

Martin Mareš

Archivum Mathematicum (2004)

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

Abstract

top
This article presents two simple deterministic algorithms for finding the Minimum Spanning Tree in O ( | V | + | E | ) 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.

How to cite

top

Mareš, 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
  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. (1926) 
  2. Frederickson G. N., Data structures for on-line updating of minimum spanning trees, SIAM J. Comput. 14 (1985), 781–798. (1985) Zbl0575.68068MR0807881
  3. Fredman M., Willard D. E., Trans-dichotomous algorithms for minimum spanning trees and shortest paths, In Proceedings of FOCS’90 (1990), 719–725. (1990) 
  4. Graham R. L., Hell P., On the history of the minimum spanning tree problem, Ann. Hist. Comput. 7 (1985), 43–57. (1985) Zbl0998.68003MR0783327
  5. Chazelle B., A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, J. ACM 47 (2000), 1028–1047. Zbl1094.68606MR1866456
  6. Karger D. R., Klein P. N., Tarjan R. E., Linear expected-time algorithms for connectivity problems, J. ACM 42 (1995), 321–328. (1995) MR1409738
  7. Matsui T., The Minimum Spanning tree Problem on a Planar Graph, Discrete Appl. Math. 58 (1995), 91–94. (1995) Zbl0823.05024MR1323024
  8. Nešetřil J., Some remarks on the history of MST-problem, Arch. Math. (Brno) 33 (1997), 15–22. (1997) MR1464297
  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. Zbl1071.05526MR2038495
  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. Zbl0999.01019
  11. Pettie S., Finding minimum spanning trees in O ( m α ( m , n ) ) time, Tech Report TR99-23, Univ. of Texas at Austin, 1999. (1999) 
  12. Pettie S., Ramachandran V., An Optimal Minimum Spanning Tree Algorithm, In Proceedings of ICALP’2000, 49–60, Springer Verlag, 2000. Zbl0973.68534MR1795885
  13. Tarjan R. E., Data structures and network algorithms, 44 CMBS-NSF Regional Conf. Series in Appl. Math. SIAM, 1983. (1983) Zbl0584.68077MR0826534

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.