Address.
Department of Applied Mathematics,
and Institute for Theoretical Computer Science (ITI), Charles University,
Malostranske nam. 25, 118 00 Praha 1, Czech Republic
E-mail. mares@kam.mff.cuni.cz
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.
AMSclassification. 05C04.
Keywords. Minor closed graph classes, minimum spanning trees.