We describe an efficient algorithm for maintaining a minimum spanning tree (MST) in a graph subject to a sequence of edge weight modifications. The sequence of minimum spanning trees is computed offline, after the sequence of modifications is known. The algorithm performs (log n) work per modification, where n is the number of vertices in the graph. We use our techniques to solve the offline geometric MST problem for a planar point set subject to insertions and deletions; our algorithm for this problem performs O(log^2 n) work per modification. No previous dynamic geometric MST algorithm was known.
Cookie Settings
eScholarship uses cookies to ensure you have the best experience on our website. You can manage which cookies you want us to use.
Our Privacy Statement includes more details on the cookies we use and how we protect your privacy.
