首页   按字顺浏览 期刊浏览 卷期浏览 An algorithm for inverse minimum spanning tree problem
An algorithm for inverse minimum spanning tree problem

 

作者: Jianzhong Zhang,   Shaoji Xu,   Zhongfan Ma,  

 

期刊: Optimization Methods and Software  （Taylor Available online 1997）
卷期: Volume 8, issue 1  

页码: 69-84

 

ISSN:1055-6788

 

年代: 1997

 

DOI:10.1080/10556789708805666

 

出版商: Gordon and Breach Science Publishers

 

关键词: Spanning Tree;Inverse Problem;Minimum Covering Set;Bipartite Graph

 

数据来源: Taylor

 

摘要:

In this paper we consider an inverse minimum spanning tree problem in which we wish to change the original weights of the edges in a graph as little as possible so that a given spanning tree of the graph can become the minimum spanning tree. An algorithm is proposed which can solve the problem in polynomial time. The algorithm is a combinatorial method that uses the minimum covering problem as its main subproblem. An example is included to illustrate the method

 

点击下载:  PDF (841KB)



返 回