北京化工大学学报(自然科学版)
北京化工大學學報(自然科學版)
북경화공대학학보(자연과학판)
JOURNAL OF BEIJING UNIVERSITY OF CHEMICAL TECHNOLOGY
2011年
1期
136-139
,共4页
最小弱顶点覆盖%次模函数%近似算法%近似度
最小弱頂點覆蓋%次模函數%近似算法%近似度
최소약정점복개%차모함수%근사산법%근사도
求给定无向图的最小弱顶点覆盖是一个NP困难问题,只能通过研究此问题的近似算法来求解.本文从基本圈出发,定义了一个次模函数,利用次模函数理论来得到一个最小弱顶点覆盖问题的近似解,且近似度为1+ln(d-1),其中d为图的顶点最大度.
求給定無嚮圖的最小弱頂點覆蓋是一箇NP睏難問題,隻能通過研究此問題的近似算法來求解.本文從基本圈齣髮,定義瞭一箇次模函數,利用次模函數理論來得到一箇最小弱頂點覆蓋問題的近似解,且近似度為1+ln(d-1),其中d為圖的頂點最大度.
구급정무향도적최소약정점복개시일개NP곤난문제,지능통과연구차문제적근사산법래구해.본문종기본권출발,정의료일개차모함수,이용차모함수이론래득도일개최소약정점복개문제적근사해,차근사도위1+ln(d-1),기중d위도적정점최대도.
