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

【文件属性】：

文件名称：分层算法求解竞赛图上的最小弱顶点覆盖 (2012年)

文件大小：747KB

文件格式：PDF

更新时间：2024-06-02 05:41:10

工程技术 论文

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