Two linear time algorithms for MST on minor closed graph classes

Martin Mares

 Department of Applied Mathematics, and Institute for Theoretical Computer Science (ITI), Charles University, Malostranske nam. 25, 118 00 Praha 1, Czech Republic


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.