%0 Journal Article
%T 严格第k最小支撑树问题
%J 系统工程理论与实践
%P 89-92
%D 2002
%X ？提出了严格第k最小树的概念.利用定长支撑树问题的复杂性,证明了求支撑树的长度分布l(g)问题是np-c的,从而证明了严格第k最小支撑树问题也是np-c的.对于k=2的情况,给出了一个多项式时间算法,其时间复杂性为$o(|ex|n^2)$,其中ex是正交换的集合,n是顶点数.
%K 严格第k最小支撑树
%K 算法
%K np-c
%U http://www.sysengi.com/CN/abstract/abstract106012.shtml