Parametric and kinetic minimum spanning trees
Parametric and kinetic minimum spanning trees
复制标题
参数和动力学最小生成树
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Monika Henzinger
中科院分区：
文献类型：
--
作者：
P. Agarwal;D. Eppstein;L. Guibas;Monika Henzinger
我们考虑参数最小跨越树问题，其中为我们提供了一个具有边缘权重的图形，该图形是参数 / spl lambda /的线性函数，并希望计算为 / spl lambda /变化的最小生成树的顺序。我们还考虑了动力学最小跨越树问题，其中 / spl lambda /代表时间，并且除了随着时间的流逝而进行的重量插入，删除和修改之外，该图还需要进行。我们在时间上解决两个问题（n/sup 2/3/log/sup 4/3/3/3/3/），在树中（或随机O（n/sup 2/3/log/log/sup 4/3/n））按更改）。我们的时间范围将平面图或其他次要次密闭家庭缩小为o（n/sup 1/2/log/log/log/sup 3/2/n）（o（n/sup 1/2/log n）随机分组）图形，o（n/sup 1/4/log/log/sup 3/2/n）每个更改（o（n/sup 1/4/log n）随机化的平面图）具有重量更改但没有插入或删除。
We consider the parametric minimum spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of minimum spanning trees generated as /spl lambda/ varies. We also consider the kinetic minimum spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.