云南大学学报（自然科学版）
雲南大學學報（自然科學版）
운남대학학보（자연과학판）
JOURNAL OF YUNNAN UNIVERSTY(NATURAL SCIENCES EDITION)
2005年
1期
1-4
,共4页
反圈%k-近似算法%最小支撑树
反圈%k-近似算法%最小支撐樹
반권%k-근사산법%최소지탱수
考虑了2个固定顶点的树划分问题,即固定k个顶点的最小和树划分问题和固定k个顶点的最小最大树划分问题,我们得到如下结果:①利用Greedy技巧,得到固定k个顶点的最小和树划分问题的最优多项式算法;②证明了固定k个顶点的最小最大树划分问题是NP-难的,并利用①的结果给出了固定k个顶点的最小最大树划分问题的一个k-近似算法.
攷慮瞭2箇固定頂點的樹劃分問題,即固定k箇頂點的最小和樹劃分問題和固定k箇頂點的最小最大樹劃分問題,我們得到如下結果:①利用Greedy技巧,得到固定k箇頂點的最小和樹劃分問題的最優多項式算法;②證明瞭固定k箇頂點的最小最大樹劃分問題是NP-難的,併利用①的結果給齣瞭固定k箇頂點的最小最大樹劃分問題的一箇k-近似算法.
고필료2개고정정점적수화분문제,즉고정k개정점적최소화수화분문제화고정k개정점적최소최대수화분문제,아문득도여하결과:①이용Greedy기교,득도고정k개정점적최소화수화분문제적최우다항식산법;②증명료고정k개정점적최소최대수화분문제시NP-난적,병이용①적결과급출료고정k개정점적최소최대수화분문제적일개k-근사산법.
