严格第k最小支撑树问题  

The Strictly kth Minimum Spanning Trees Problems

作　　者：李帮义[1] 姚恩瑜[2] 

机构地区：[1]南京航空航天大学经济管理学院,江苏南京210016 [2]浙江大学应用数学系,浙江杭州310027

出　　处：《系统工程理论与实践》2002年第1期89-92,共4页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金 ( 1 9971 0 78);南航航空基金 ( S0 1 33-0 92 )

摘　　要：提出了严格第 k最小树的概念 .利用定长支撑树问题的复杂性 ,证明了求支撑树的长度分布L( G)问题是 NP-C的 ,从而证明了严格第 k最小支撑树问题也是 NP-C的 .对于 k=2的情况 ,给出了一个多项式时间算法 ,其时间复杂性为 O( | EX| n2 ) ,其中 EX是正交换的集合 。The paper puts forward the concept of strictly kth minimum spanning trees. Using the fixed length spanning tree problem,it proves that finding the spanning tree length distributions problem is NP-C, so the strictly kth minimum spanning trees problems is also proven to be NP-C. For the special case $k=2$, an polynomial algorithm is given, whose time complexity is $O(|EX|×n+2$,where %EX% is the set of all positive exchanges, $n$ is the number of vertexes.;

关 键 词：严格第k最小支撑树 算法 NP-C 赋权图 图论 

分 类 号：O157.5[理学—数学] O224[理学—基础数学]