Geodesic
Two linear time algorithms for MST on minor closed graph classes
Archivum mathematicum, Tome 40 (2004) no. 3, pp. 315-320.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2004},
     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
PB  - mathdoc
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
%I mathdoc
%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/