%0 Journal Article
%T 次模函数近似算法求最小弱顶点覆盖
%A 涂建华
%A 高昊宇
%A 赖文华
%J 北京化工大学学报(自然科学版)
%D 2011
%X 求给定无向图的最小弱顶点覆盖是一个NP困难问题，只能通过研究此问题的近似算法来求解。本文从基本圈出发，定义了一个次模函数，利用次模函数理论来得到一个最小弱顶点覆盖问题的近似解，且近似度为1+ln(d-1)，其中d为图的顶点最大度。
%U http://www.journal.buct.edu.cn/CN/abstract/abstract14723.shtml