Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph | Computer Science Department at Princeton University

Report ID:

TR-243-90

Authors:

Eppstein, David / Italiano, Guiseppe F. / Tamassia, Roberto / Tarjan, Robert E. / Westbrook, Jeffrey / Yung, Moti

Date:

December 1989

Pages:

Download Formats:

[PDF]

Abstract:

We give effcient algorithms for maintaining a minimum spanning forest of a planar graph subject to on-line modifications. The modifications supported include changes in the edge weights, and insertion.