摘要： 图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为wv,所有边的权重均为we,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。
| [1] ALAVI Y,BEHZAD M,LESNIAK-FOSTER L M,et al.Total matchings and total coverings of graphs[J].Journal of Graph Theory,1977,1(2):135-140. [2] LAN J K,CHANG G J.On the mixed domination problem in graphs [J].Theoretical Computer Science,2013,476(476):84-93. [3] MANLOVE D F.On the algorithmic complexity of twelve cove-ring and independence parameters of graphs[J].Discrete Applied Mathematics,1999,91(1-3):155-175. [4] ALAVI Y,LIU J,WANG J,et al.On total covers of graphs[J].Discrete Mathematics,1992,100(1-3):229-233. [5] ZHAO Y,KANG L,SOHN M Y.The algorithmic complexity of mixed domination in graphs [J].Theoretical Computer Science,2011,412(22):2387-2392. [6] GAREY M R,JOHNSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].W.H.Freeman and Company,1979. [7] BERTOSSI A A.Dominating sets for split and bipartite graphs[J].Information Processing Letters,1984,19(1):37-40. [8] PAPADIMITRIOU C H,STEIGLITZ K.Combinatorial optimization:algorithms and complexity[M].Prentice Hall,1998. [9] JOHNSON D S.Approximation algorithms for combinatorialproblems[J].Journal of Computer and System Sciences,1982,9(3):256-278. [10] FUJITO T,NAGAMOCHI H.A 2-approximation algorithm for the minimum weight edge dominating set problem [J].Discrete Applied Mathematics,2002,118(3):199-207. [11] NEMHAUSER G L,JR L E Trotter.Properties of vertex pac-king and independence system polyhedra[J].Mathematical Programming,1974,6(1):48-61. [12] YANNAKAKIS M,GAVRIL F.Edge Dominating Sets inGraphs[J].SIAM Journal on Applied Mathematics,1980,38(3):364-372. [13] NIEBERG T,HURINK J.A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs[M]∥Approximation and Online Algorithms.Springer Berlin Heidelberg,2005:296-306. [14] HEDETNIEMI S T,LASKAR R C.Bibliography on domination in graphs and some basic definitions of domination parameters[J].Discrete Mathematics,1991,86(1):257-277. [15] XIAO M,KLOKS T,POON S H.New parameterized algorithms for edge dominating set[J].Theoretical Computer Science,2013,4(511):147-158. [16] HATAMI P.An approximation algorithm for the total covering problem[J].Discussiones Mathematicae Graph Theory,2007,27(3):553-558. [17] RAZ R,SAFRA S.A sub-constant error-probability low-degree test,and a sub-constant error-probability PCP characterization of NP[C]∥Proceedings of Twenty-Ninth ACM Symposium on Theory of Computing(STOC).ACM,1997:475-484. |
| No related articles found! |
|
||
首页