Stability analysis of the minimum spanning tree problem

摘要: 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 edge weights. weights are subject to perturbations. stability solutions analyzed. Formulas for radius derived, and polynomial algorithms its computation designed.