Publication Date

1995

Technical Report Number

TR95-06

Subjects

Mathematics of Computing, Computer Applications, Software

Abstract

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.

Share

COinS