Offline Algorithms for Dynamic Minimum Spanning Tree Problems
Offline Algorithms for Dynamic Minimum Spanning Tree Problems
复制标题
动态最小生成树问题的离线算法
DOI：
--
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
D. Eppstein
中科院分区：
文献类型：
--
作者：
D. Eppstein
我们描述了一个有效的算法，用于维护最小生成树（MST）在一个图中的一系列的边权重修改。在已知修改序列之后，离线计算最小生成树序列。算法每次修改执行O（log n）的工作，其中n是图中的顶点数。我们使用我们的技术来解决离线几何MST问题的平面点集插入和删除，我们的算法为这个问题进行O（log2n）的工作每次修改。没有以前的动态几何MST算法是已知的。
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 O(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(log2n) work per modification. No previous dynamic geometric MST algorithm was known.