次模函数近似算法求最小弱顶点覆盖 (2011年)

【文件属性】：

文件名称：次模函数近似算法求最小弱顶点覆盖 (2011年)

文件大小：761KB

文件格式：PDF

更新时间：2024-06-17 16:09:21

工程技术 论文

求给定无向图的最小弱顶点覆盖是一个NP困难问题，只能通过研究此问题的近似算法来求解。本文从基本圈出发，定义了一个次模函数，利用次模函数理论来得到一个最小弱顶点覆盖问题的近似解，且近似度为1+ In(d-1)，其中d为图的顶点最大度。