张佳男,肖鸣宇.带权混合支配问题的近似算法研究[J].计算机科学,2018,45(4):83-88
带权混合支配问题的近似算法研究
Approximation Algorithm for Weighted Mixed Domination Problem
投稿时间:2017-05-31  修订日期:2017-07-30
DOI:10.11896/j.issn.1002-137X.2018.04.012
中文关键词:  混合支配问题,近似算法,点覆盖,线性规划
英文关键词:Mixed domination problem,Approximation algorithm,Vertex cover problem,Linear programming
基金项目:本文受国家自然科学基金项目(61772115,61370071),中央高校基本科研业务费专项资金项目(ZYGX2015J057)资助
作者单位E-mail
张佳男 电子科技大学计算机科学与工程学院 成都611731 william.jn.zhang@gmail.com 
肖鸣宇 电子科技大学计算机科学与工程学院 成都611731 myxiao@uestc.edu.cn 
摘要点击次数: 303
全文下载次数: 276
中文摘要:
      图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为wv,所有边的权重均为we,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。
英文摘要:
      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.
查看全文  查看/发表评论  下载PDF阅读器