科技传播
科技傳播
과기전파
PUBLIC COMMUNICATION OF SCIENCE & TECHNOLOGY
2014年
15期
140-141
,共2页
杨惠娟%李春娥%严佩升
楊惠娟%李春娥%嚴珮升
양혜연%리춘아%엄패승
推广%最小k--cut问题%近似算法
推廣%最小k--cut問題%近似算法
추엄%최소k--cut문제%근사산법
原始割集问题是图论几大经典问题之一，在实际中应用广泛。割集问题有很多较为复杂的推广问题，如最小multicut问题和最小multiwaycut问题等。本文主要讨论的是割集问题的另一推广问题最小k--cut问题，并且给出了一个时间复杂度为)O(m log2 m 的近似算法求得该问题的可行解。
原始割集問題是圖論幾大經典問題之一，在實際中應用廣汎。割集問題有很多較為複雜的推廣問題，如最小multicut問題和最小multiwaycut問題等。本文主要討論的是割集問題的另一推廣問題最小k--cut問題，併且給齣瞭一箇時間複雜度為)O(m log2 m 的近似算法求得該問題的可行解。
원시할집문제시도론궤대경전문제지일，재실제중응용엄범。할집문제유흔다교위복잡적추엄문제，여최소multicut문제화최소multiwaycut문제등。본문주요토론적시할집문제적령일추엄문제최소k--cut문제，병차급출료일개시간복잡도위)O(m log2 m 적근사산법구득해문제적가행해。
