Two linear time algorithms for MST on minor closed graph classes.

MaRDI QIDQ3435477zbMATH OpenFDO

Authors Martin Mareš

Publication date 26 April 2007

Full work available at URL https://eudml.org/doc/127685, http://www.emis.de/journals/AM/04-3/index.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

minimum spanning treedeterministic algorithms

Mathematics Subject Classification ID

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

Recommendations

• An optimal parallel algorithm for minimum spanning trees in planar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• The minimum spanning tree problem on a planar graph
• An optimal minimum spanning tree algorithm

Cited in

(11)

• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Counting and sampling minimum cuts in genus \(g\) graphs
• Contracting a planar graph efficiently
• Data-oblivious graph algorithms in outsourced external memory
• A linear-time algorithm for finding a minimum spanning pseudoforest
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
• Global minimum cuts in surface embedded graphs
• Minimum Cuts in Surface Graphs
• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• The saga of minimum spanning trees

This page was built for publication: Two linear time algorithms for MST on minor closed graph classes.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3435477)