Computer Science ›› 2018, Vol. 45 ›› Issue (4): 83-88.doi: 10.11896/j.issn.1002-137X.2018.04.012

Previous Articles     Next Articles

Approximation Algorithm for Weighted Mixed Domination Problem

ZHANG Jia-nan and XIAO Ming-yu   

  • Online:2018-04-15 Published:2018-05-11

Abstract: 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.

Key words: Mixed domination problem,Approximation algorithm,Vertex cover problem,Linear programming

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!