运筹与管理
運籌與管理
운주여관리
OPERATIONS RESEARCH AND MANAGEMENT SCIENCE
2007年
5期
83-86
,共4页
运筹学%图的控制集%近似算法%NP-困难
運籌學%圖的控製集%近似算法%NP-睏難
운주학%도적공제집%근사산법%NP-곤난
部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小.本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明.
部分控製集問題是對于給定的頂點賦權圖G=(V,E;c)和正整數K,尋找圖G一箇頂點子集T,使得在其控製下的頂點箇數不小于K且T中頂點權和達到最小.本文討論瞭部分控製集問題的NP-睏難性;給齣瞭該問題的一種脩正Greedy近似算法,併對其近似度H(K)給齣瞭證明.
부분공제집문제시대우급정적정점부권도G=(V,E;c)화정정수K,심조도G일개정점자집T,사득재기공제하적정점개수불소우K차T중정점권화체도최소.본문토론료부분공제집문제적NP-곤난성;급출료해문제적일충수정Greedy근사산법,병대기근사도H(K)급출료증명.
