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

摘要：

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

关键词：最小弱顶点覆盖、次模函数、近似算法、近似度

所属期刊栏目：38

分类号：O157(代数、数论、组合理论)

资助基金：中央高校基本科研业务费专项资金QN0913

在线出版日期：2011-04-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：136-139