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