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   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .