带权混合支配问题的近似算法研究

摘要

A mixed domination set of graph G =(V,E) is a set D with vertexes and edges in graph G,thus for every edge or vertex in G,if it is not in D,it must be adjacent or incident to at least one vertex or edge in D.The mixed domination problem is to find a mixed domination set with minimum cardinality.The mixed domination problem combines both the vertex domination problem and the edge domination problem,it is NP-complete and has many applications in real life.The weighted mixed domination set problem is a generalization of the mixed domination set problem,where a weight wv is set to each vertex and a weight we is set to each edge,and the problem is to find a mixed domination set for minimum weight.Although the mixed domination set problem has a 2-approximation algorithm,few approximation results are known for the weighted mixed domination set problem.This paper designed a 3-approximation algorithm for the weighted mixed domination set problem with constraint wv≤we.%图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻.混合支配问题是在一个图中找到一个基数最小的混合支配集.混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注.混合支配问题在一般图上是NP完全的.带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分.令图中所有点的权重均为wv,所有边的权重均为we,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小.尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢.在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法.