Increasing the weight of minimum spanning trees
Increasing the weight of minimum spanning trees
复制标题
增加最小生成树的权重
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Roberto Solis
中科院分区：
文献类型：
--
作者：
G. Frederickson;Roberto Solis
摘要研究了图的最小生成树的权的最大增加量的计算问题，该最大增加量是由去掉给定数目的边或边的权的有限增加引起的。对于边去除的情形，证明了该问题是NP-难的，并给出了一个Ω（1/logk）-近似算法，其中（输入参数）k > 1是要去除的边数.第二个问题进行了研究，假设边的权重的增加具有与变化的幅度成比例的相关成本。给出了一个O（n3 m2 log（n2/ m））时间的算法来求解.
Abstract The problems of computing the maximum increase in the weight of the minimum spanning trees of a graph caused by the removal of a given number of edges, or by finite increases in the weights of the edges, are investigated. For the case of edge removals, the problem is shown to be NP-hard and an Ω(1/log k )-approximation algorithm is presented for it, where (input parameter) k > 1 is the number of edges to be removed. The second problem is studied, assuming that the increase in the weight of an edge has an associated cost proportional to the magnitude of the change. An O ( n 3 m 2 log( n 2 / m )) time algorithm is presented to solve it.