Offline Algorithms for Dynamic Minimum Spanning Tree Problems

✍ Scribed by D. Eppstein

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 651 KB
• Volume: 17
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1994.1033

✦ Synopsis

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 takes time (O(k \log n)) for a sequence of (k) updates to a graph of (n) vertices, giving a bound of (O(\log n)) on the average time per update. 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 takes time (O\left(k \log ^{2} n\right)), for an average of (O\left(\log ^{2} n\right)) time per update. We describe a further refinement of our technique which solves the problem in the rectilinear metric in time (O(k \log n \log \log n)), for an average of (O(\log n \log \log n)) time per update. 1994 Academic Press. Inc.