| ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES |
| |
| 作者姓名： | Bangyi LI Zhaohan SHENG
College of Economics and Management Nanjing University of Aeronautics and Astronautics
Nanjing China
Graduate School of Management Science and Engineering Nanjing University Nanjing China |
| |
| 作者单位： | Bangyi LI Zhaohan SHENG
College of Economics and Management，Nanjing University of Aeronautics and Astronautics
Nanjing 210016，China
Graduate School of Management Science and Engineering，Nanjing University Nanjing 210093，China |
| |
| 摘 要： | Let G=be a network with the vertex set V,the edge set E and the length vector L, andlet T~* be a prior determined spanning tree of G. The inverse minimum spanning tree problem withminimum number of perturbed edges is to perturb the length vector L to L+δ, such that T~* is one ofminimum spanning trees under the length vector L+δ and the number of perturbed edges is minimum.This paper establishes a mathematical model for this problem and transforms it into a minimumvertex covering problem in a bipartite graph G_0, a path-graph. Thus a strongly polynomial algorithmwith time complexity O(mn~2) can be designed by using Hungarian method.
|
| 关 键 词： | 最小生成树 最小数 边缘扰动 倒置网络最优化问题 数学模型 最小顶点覆盖问题 多项式算法 |
On the inverse minimum spanning tree problem with minimum number of perturbed edges |
| |
| Bangyi LI Zhaohan SHENG
College of Economics and Management,Nanjing University of Aeronautics and Astronautics
Nanjing ,China
Graduate School of Management Science and Engineering,Nanjing University Nanjing ,China.ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES[J].Journal of Systems Science and Systems Engineering,2003,12(3):350-359. |
| |
| Authors: | Bangyi Li Zhaohan Sheng |
| |
| Institution: | 1. College of Economics and Management, Nanjing University of Aeronautics and Astronautics Nanjing 210016, China;Graduate School of Management Science and Engineering, Nanjing University Nanjing 210093, China libangyi@263. net
2. Graduate School of Management Science and Engineering, Nanjing University Nanjing 210093, China |
| |
| Abstract: | Let G= be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+ , such that T* is one of minimum spanning trees under the length vector L+ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G0, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn2) can be designed by using Hungarian method. |
| |
| Keywords: | Inverse network optimization problem minimum spanning tree vertex covering set |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
