计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 83-88.doi: 10.11896/j.issn.1002-137X.2018.04.012

• 2017年全国理论计算机科学学术年会 • 上一篇    下一篇

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

张佳男,肖鸣宇   

  1. 电子科技大学计算机科学与工程学院 成都611731,电子科技大学计算机科学与工程学院 成都611731
  • 出版日期:2018-04-15 发布日期:2018-05-11
  • 基金资助:
    本文受国家自然科学基金项目(61772115,61370071),中央高校基本科研业务费专项资金项目(ZYGX2015J057)资助

Approximation Algorithm for Weighted Mixed Domination Problem

ZHANG Jia-nan and XIAO Ming-yu   

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

摘要: 图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为wv,所有边的权重均为we,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。

关键词: 混合支配问题,近似算法,点覆盖,线性规划

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]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[3] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[4] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[5] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[6] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .