系统工程理论与实践
繫統工程理論與實踐
계통공정이론여실천
SYSTEMS ENGINEERING--THEORY & PRACTICE
2002年
1期
89-92
,共4页
严格第k最小支撑树%算法%NP-C
嚴格第k最小支撐樹%算法%NP-C
엄격제k최소지탱수%산법%NP-C
提出了严格第k最小树的概念.利用定长支撑树问题的复杂性,证明了求支撑树的长度分布L(G)问题是NP-C的,从而证明了严格第k最小支撑树问题也是NP-C的.对于k=2的情况, 给出了一个多项式时间算法,其时间复杂性为O(|EX|n2),其中 EX是正交换的集合,n是顶点数.
提齣瞭嚴格第k最小樹的概唸.利用定長支撐樹問題的複雜性,證明瞭求支撐樹的長度分佈L(G)問題是NP-C的,從而證明瞭嚴格第k最小支撐樹問題也是NP-C的.對于k=2的情況, 給齣瞭一箇多項式時間算法,其時間複雜性為O(|EX|n2),其中 EX是正交換的集閤,n是頂點數.
제출료엄격제k최소수적개념.이용정장지탱수문제적복잡성,증명료구지탱수적장도분포L(G)문제시NP-C적,종이증명료엄격제k최소지탱수문제야시NP-C적.대우k=2적정황, 급출료일개다항식시간산법,기시간복잡성위O(|EX|n2),기중 EX시정교환적집합,n시정점수.
