作者：张佳男; 肖鸣宇混合支配问题近似算法点覆盖线性规划
摘要：图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为w v,所有边的权重均为w e,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
