Fernandez-Baca, David and Slutzki, Giora (1995) Linear-Time Algorithms for Parametric Minimum Spanning Tree Problems on Planar Graphs. Technical Report TR95-06, Department of Computer Science, Iowa State University.
Linear-Time Algorithms for Parametric
Minimum Spanning Tree Problems on
David Fernandez-Baca and Giora Slutzki
A linear-time algorithm for the minimum-ratio spanning tree problem on
planar graphs is presented. The algorithm is based on a new planar minimum
spanning tree algorithm. The approach extends to other parametric minimum
spanning tree problems on planar graphs and to other families of graphs
having small separators.
Contact site administrator at: email@example.com