河北师范大学学报—

期刊信息

刊名：河北师范大学学报（自然科学版）Journal of Hebei Normal University (Natural Science)
主办：河北师范大学
ISSN： 1000-5854
CN： 13-1061/N
中国科技核心期刊
中国期刊方阵入选期刊
中国高校优秀科技期刊
华北优秀期刊
河北省优秀科技期刊

协同采编系统

友情链接

带线性惩罚的次模边点控制集问题的近似算法

(河北师范大学数学科学学院，河北石家庄 050024)
DOI： 10.13763/j.cnki.jhebnu.nse.202301004

An Approximation Algorithm for the Submodular Edge Vertex Domination Set Problem with Linear Penalties

PDF
下载
HTML

摘要/Abstract

摘要：

考虑带线性惩罚的次模边点控制集问题，给定一个无向图G=(V,E)，且V中每个顶点都有一个非负惩罚，E 的每个边子集都有一个非负权值.称e={μ,υ}∈E为边点控制顶点w，如果w∈N [μ]∪N [υ]，这里N [μ]，N [υ]分别为顶点μ，υ的闭邻域.带线性惩罚的次模边点控制集问题的目标是寻找一个边子集D，使得D的权值与未被D边点控制的顶点的惩罚费用之和最小.利用原始对偶技巧给出此问题的一个k-近似算法，其中k=max_υ∈v |N [υ]|.

Abstract：

In this paper，we consider the submodular edge vertex domination set problem with linear penalties.In this problem，we are given an undirected graph G=(V，E) with a nonnegative penalty for each vertex and a nonnegative cost for each edge subset.An edge e={μ,υ}in E is called to edge vertex dominate a vertex w,whenever w is in N [μ]∪N[υ]，where N[μ]，N[υ] are the closed neighborhoods of μ，υ respectively.The goal of the submodular edge vertex domination set problem with linear penalties is to find an edge subset D such that the sum of the cost of D and the penalties of the undominated vertices by D is minimized.In this paper，we mainly use the primal dual technique to get a k-approximation algorithm for the submodular edge vertex domination set problem with linear penalties，where k=max_υ∈v |N [υ]|.

关键词

关键词： 边点控制 ; 次模 ; 惩罚 ; 原始对偶

Key words： edge vertex domination ; submodular ; penalty ; primal dual

参考文献 22

[1] HAYNES T W，HEDETNIEMI S T，SLATER P J. Fundamentals of Domination in Graphs[M]. New York:Marcel Dekker，1998.
[2] YANG Y，WANG J，MOTTER A E. Network Observability Transitions[J]. Physical Review Letters，2012，109:258701. doi:10. 1103/PhysRevLett. 109. 258701
[3] ECHENIQUE P，GOMEZ-GARDENES J，MORENO Y，et al. Distanced Covering Problems in Scale-free Networks with Degree Correlations[J]. Physical Review E，2005，71:035102. doi:10. 1103/PhysRevE. 71. 035102
[4] TAKAGUCHI T，HASEGAWA T，YOSHIDA Y. Suppressing Epidemics on Networks by Exploiting Observer Nodes[J]. Physical Review E，2014，90:012807. doi:10. 1103/physreve. 90. 012807
[5] LIU Y Y，SLOTINE J J，BARABASI A L. Controllability of Complex Networks[J]. Nature，2011，473:167-173. doi:10. 1038/nature10011
[6] WUCHTY S. Controllability in Protein Interaction Networks[J]. Proceedings of the National Academy of Sciences of the United States of America，2014，111:7156-7160. doi:10. 1073/pnas. 1311231111
[7] WU J，LI H. A Dominating-set-based Routing Scheme in Ad Hoc Wireless Networks[J]. Telecommunication Systems，2001，18:13-36. doi:10. 1002/0471224561. ch20
[8] BRAMOULLE Y，KRANTON R. Public Goods in Networks[J]. Journal of Economic Theory，2007，135:478-494. doi:10. 1016/j. jet. 2006. 06. 006
[9] GAREY M R,JOHNSON D S. Computers and Intractability:A Guide to the Theory of NP-completeness[C]∥HARTMANIS J. Siam Rewiew 24,1982:90-91. doi:10. 1137/1024022
[10] GUHA S，KHULLER S. Approximation Algorithms for Connected Dominating Sets[J]. Algorithmica，1998，20:374-387. doi:10. 1007/s00453-007-9015-8
[11] RUAN L，DU H，JIA X，et al. A Greedy Approximation for Minimum Connected Dominating Sets[J]. Theoretical Computer Science，2004，329:325-330. doi:10. 1016/j. tcs. 2004. 08. 013
[12] PETERS K. Theoretical and Algorithmic Results on Domination and Connectivity[D]. Clemson:Clemson University，1986.
[13] LEWIS J R. Vertex-edge and Edge-vertex Parameters in Graphs[D]. Clemson:Clemson University，2007.
[14] KRISHNAKUMARI B，VENKATAKRISHNAN Y B，KRZYWKOWSKT M. On Trees with Total Domination Number Equal to Edge-vertex Domination Number Plus One[J]. Indian Academy of Sciences，2016，126:153-157. doi:10. 1007/s12044-016-0267-6
[15] VENKATAKRISHNAN Y B，KRISHNAKUMARI B. An Improved Upper Bound of Edge-vertex Domination Number of a Tree[J]. Information Processing Letters，2018，134:14-17. doi:10. 1016/j. ipl. 2018. 01. 012
[16] SAHIN A，SAHIN B. Total Edge-vertex Domination[J]. Theoretical Informatics and Applications，2020，54：1-7. doi:10. 1051/ita/2020001
[17] THAKKAR D K，JAMVECHA N P. Edge-vertex Domination in Graphs[J]. International Journal of Mathematics and Its Applications，2018，6(1):549-555. doi:10. 48550/arXiv. 2111. 13552
[18] IOSINGIREDDY V R，BASAPPA M. Edge-vertex Dominating Set in Unit Disk Graphs[cs. CG]. 2022，arXiv:2111. 13552v1[18]IOANNIS L，IOANNIS S，VASSILIS Z. Improved Budgeted Connected Domination and Budgeted Edge-vertex Domination[J]. Theoretical Computer Science，2021，858:1-12. doi:10. 1016/J. TCS. 2021. 01. 030
[19] DU S J，GAO S G，HOU B，et al. An Approximation Algorithm for Submodular Hitting Set Problem with Linear Penalties[J]. Journal of Combinatorial Optimization，2020，40:1065-1074. doi:10. 1007/s10878-020-00653-6
[20] HOU C F，GAO S G，LIU W，et al. An Approximation Algorithm for The Submodular Multicut Problem in Trees with Linear Penalties[J]. Optimization Letters，2021，15:1105-1112. doi:10. 1007/s11590-020-01665-1
[21] XU D C，WANG F M，DU D L，et al. Approximation Algorithm for Submodular Vertex Cover Problems with Linear/Submodular Penalties Using Primal-dual Technique[J]. Theoretical Computer Science，2016，630:117-125. doi:10. 1016/j. tcs. 2016. 04. 005
[22] FLEISCHER L，IWATA S. A Push-relabel Framework for Submodular Function Minimization and Applications to Parametric Optimization[J]. Discrete Appl Math，2003，131:311-322. doi:10. 1016/S0166-218X(02)00458-4