Stability analysis of the minimum spanning tree problem
Stability analysis of the minimum spanning tree problem
复制标题
最小生成树问题的稳定性分析
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
E. Gordeev
中科院分区：
文献类型：
--
作者：
E. Gordeev
研究了拟阵上的一个著名的优化问题--最小生成树问题。在边权矩阵空间中引入了范数L 1。边权重受扰动的影响。分析了该问题解的稳定性。推导了稳定半径的计算公式，设计了计算稳定半径的多项式算法。
A well-known optimization problem on matroids-the minimum spanning tree problem-is examined. The norm l 1 is introduced in the space of matrices of edge weights. The edge weights are subject to perturbations. The stability of solutions to the problem is analyzed. Formulas for the stability radius are derived, and polynomial algorithms for its computation are designed.