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

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