分层算法求解竞赛图上的最小弱顶点覆盖

摘要：

竞赛图上的弱顶点覆盖问题是一个NP困难问题,本文先定义了竞赛图上的势加权函数,然后利用分层技术给出了一个求解竞赛图最小弱顶点覆盖问题的近似算法,并证明了此近似算法的近似度为3.

关键词：竞赛图、弱顶点覆盖、分层算法、势加权函数

所属期刊栏目：39

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

资助基金：中央高校基本科研业务费ZZ1133

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

页数：共3页

页码：103-105