LINEAR-TIME ALGORITHMS FOR PARAMETRIC MINIMUM SPANNING TREE PROBLEMS ON PLANAR GRAPHS

Authors
FERNANDEZBACA D SLUTZKI G
Citation
D. Fernandezbaca et G. Slutzki, LINEAR-TIME ALGORITHMS FOR PARAMETRIC MINIMUM SPANNING TREE PROBLEMS ON PLANAR GRAPHS, Theoretical computer science, 181(1), 1997, pp. 57-74
Citations number
35
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
181
Issue
1
Year of publication
1997
Pages
57 - 74
Database
ISI
SICI code
0304-3975(1997)181:1<57:LAFPMS>2.0.ZU;2-M
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 mi nimum spanning tree algorithm. The approach extends to other parametri c minimum spanning tree problems on planar graphs and to other familie s of graphs having small separators.