zbMATH — the first resource for mathematics

Two linear time algorithms for MST on minor closed graph classes. (English) Zbl 1116.05079
Summary: 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.

05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
Full Text: EuDML EMIS