北京化工大学学报（自然科学版）
北京化工大學學報（自然科學版）
북경화공대학학보（자연과학판）
JOURNAL OF BEIJING UNIVERSITY OF CHEMICAL TECHNOLOGY(NATURAL SCIENCE EDITION)
2012年
1期
103-105
,共3页
竞赛图%弱顶点覆盖%分层算法%势加权函数
競賽圖%弱頂點覆蓋%分層算法%勢加權函數
경새도%약정점복개%분층산법%세가권함수
竞赛图上的弱顶点覆盖问题是一个NP困难问题,本文先定义了竞赛图上的势加权函数,然后利用分层技术给出了一个求解竞赛图最小弱顶点覆盖问题的近似算法,并证明了此近似算法的近似度为3.
競賽圖上的弱頂點覆蓋問題是一箇NP睏難問題,本文先定義瞭競賽圖上的勢加權函數,然後利用分層技術給齣瞭一箇求解競賽圖最小弱頂點覆蓋問題的近似算法,併證明瞭此近似算法的近似度為3.
경새도상적약정점복개문제시일개NP곤난문제,본문선정의료경새도상적세가권함수,연후이용분층기술급출료일개구해경새도최소약정점복개문제적근사산법,병증명료차근사산법적근사도위3.
