archives

Linear-Time Algorithms for Parametric Minimum Spanning Tree Problems on Planar Graphs


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

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.

Full text available as:Postscript
Adobe PDF

Abstract

Linear-Time Algorithms for Parametric
Minimum Spanning Tree Problems on
Planar Graphs
by
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.

Subjects:All uncategorized technical reports
ID code:00000096
Deposited by:Staff Account on 01 March 1995



Contact site administrator at: ssg@cs.iastate.edu