A greedy algorithm for the minimum \(2\) -connected 详细信息    查看全文

• 作者：Yishuo Shi ; Yaping Zhang ; Zhao Zhang ; Weili Wu
• 关键词：Fault ; tolerant connected dominating set ; Greedy algorithm ; Non ; submodular potential function
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：31
• 期：1
• 页码：136-151
• 全文大小：684 KB
• 参考文献：Bondy JA, Murty USR (2008) Graph theory. Springer, New YorkCrossRef MATH
  Cheng X, Huang X, Li D, Wu W, Du D-Z (2003) A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42:202–208MathSciNet CrossRef MATH
  Dai F, Wu J (2006) On constructing \(k\) -connected \(k\) -dominating set in wireless ad hoc and sensor networks. J Parallel Distrib Comput 66:947–958CrossRef MATH
  Das B, Bharghavan V (1997) Routing in ad hoc networks using minimum connected dominating sets. In: ICC’97, Montreal, Canada, pp 376–380.
  Du D.-Z, Graham R.L, Pardalos P.M, Wan P.-J, Wu W, Zhao W (2008) Analysis of greedy approximation with nonsubmodular potential functions. In: Proceedings of the 19th ACMSIAM Symposium on Discrete Algorithms, pp 167–175.
  Du D-Z, Ko K-I, Hu X (2012) Design and analysis of approximation algorithms. Springer, New YorkCrossRef MATH
  Du D-Z, Wan P-J (2012) Connected dominating set: theory and applications. Springer, New YorkMATH
  Ephremides A, Wieselthier J, Baker D (1987) A design concept for reliable mobile radio networks with frequency hopping signaling. Proc IEEE 759:56–73CrossRef
  Fleischer L, Jain K, Williamson DP (2006) Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J Comput Syst Sci 72:838–867MathSciNet CrossRef MATH
  Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New YorkMATH
  Gropl C, Hougardy S, Nierhoff T, Promel HJ (2001) Approximation algorithms for the Steiner tree problem in graphs. In: Du D-Z, Cheng X (eds) Steiner trees in industries. Kluwer, Dordrecht, pp 235–279CrossRef
  Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20:374–387MathSciNet CrossRef MATH
  Guha S, Khuller S (1999) Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf Comput 150:57–74MathSciNet CrossRef MATH
  Kim D, Wang W, Li X, Zhang Z (2010)Wu W. A new constant factor approximation for computing \(3\) -connected \(m\) -dominating sets in homogeneous wireless networks. In: IEEE INFOCOM, pp 1–9.
  Li D, Liu L, Yang H (2009) Minimum connected \(r\) -hop \(k\) -dominating set in wireless networks. Discrete Math Algorithms Appl 1:45–58MathSciNet CrossRef MATH
  Li Y, Wu Y, Ai C, Beyah R (2012) On the construction of \(k\) -connected \(m\) -dominating sets in wireless networks. J Comb Optim 23:118–139MathSciNet CrossRef MATH
  Misra S, Hong S, Xue G, Tang J (2010) Constrained realy node placement in wireless sensor networks: formulation and approximations. IEEE/ACM Trans Netw 18:434–447CrossRef
  Nutov Z (2010) Approximating Steiner networks with node-weights. SIAM J Comput 39:3001–3022MathSciNet CrossRef MATH
  Ruan L, Du H, Jia X, Wu W, Li Y, Ko K (2004) A greedy approximation for minimum connected dominating sets. Theor Comput Sci 329:325–330MathSciNet CrossRef MATH
  Shang W, Yao F, Wan P-J, Hu X (2008) On minimum \(m\) -connected \(k\) -dominating set problem in unit disc graphs. J Comb Optim 16:99–106MathSciNet CrossRef MATH
  Thai MT, Zhang N, Tiwari R, Xu X (2007) On approximation algorithms of \(k\) -connected \(m\) -dominating sets in disk graphs. Theor Comput Sci 385:49–59MathSciNet CrossRef MATH
  Vazirani VV (2001) Approximation algorithms. Springer, New YorkMATH
  Wan P-J, Alzoubi KM, Frieder O (2004) Distributed construction of connected dominating set in wireless ad hoc networks. ACM/Springer Mob Netw Appl 9:141–149CrossRef
  Wang F, Thai MT, Du D-Z (2009) On the construction of 2-connected virtual backbone in wireless networks. IEEE Trans Wirel Commun 8:1230–1237CrossRef
  Wang W, Kim D, An M, Gao W, Li X, Zhang, Wu W (2012) On construction of quality fault-tolerant virtual backbone in wireless networks. IEEE/ACM Trans Netw. doi:10.​1109/​TNET.​2012.​2227791 .
  Wu Y, Wang F, Thai M.T, Li Y.(2007) Constructing \(k\) -connected \(m\) -dominating sets in wireless sensor networks. In: Military communications conference, Orlando, FL
  Yang D, Misra S, Fang X, Xue G, Zhang J (2012) Two-tiered constrained relay node placement in wireless sensor networks: computational complexity and efficient approximations. IEEE Trans Mob Comput 11:1399–1411CrossRef
  Zelikovsky A (1996) Better approximation bounds for the network and euclidean Steiner tree problems. Technical report CS-96-06, Department of Computer Science, University of Vir- ginia, Charlottesville
  Zhang Z, Gao X, Wu W, Du D-Z (2009) A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks. J Glob Optim 45:451–458MathSciNet CrossRef MATH
  Zhang Z, Liu Q, Li D (2009) Two algorithms for connected \(r\) -hop \(k\) -dominationg set. Discrete Math Algorithms Appl 1:485–498MathSciNet CrossRef MATH
  Zhou J, Zhang Z, Wu W, Xing X. A Greedy algorithm for the fault-tolerant connected dominating set in a general graph. J. Combinatorial, Optimization. doi:10.​1007/​s10878-013-9638-4 .
  
• 作者单位：Yishuo Shi (1)
  Yaping Zhang (1)
  Zhao Zhang (1)
  Weili Wu (2)
  
  1. College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, Xinjiang, People’s Republic of China
  2. Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75080, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

To save energy and alleviate interference in a wireless sensor network, connected dominating set (CDS) has been proposed as the virtual backbone. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a \(k\)-connected \(m\)-fold dominating set \(((k,m)\)-CDS for short): a subset of nodes \(C\subseteq V(G)\) is a \((k,m)\)-CDS of \(G\) if every node in \(V(G)\setminus C\) is adjacent with at least \(m\) nodes in \(C\) and the subgraph of \(G\) induced by \(C\) is \(k\)-connected.In this paper, we present an approximation algorithm for the minimum \((2,m)\)-CDS problem with \(m\ge 2\). Based on a \((1,m)\)-CDS, the algorithm greedily merges blocks until the connectivity is raised to two. The most difficult problem in the analysis is that the potential function used in the greedy algorithm is not submodular. By proving that an optimal solution has a specific decomposition, we managed to prove that the approximation ratio is \(\alpha +2(1+\ln \alpha )\), where \(\alpha \) is the approximation ratio for the minimum \((1,m)\)-CDS problem. This improves on previous approximation ratios for the minimum \((2,m)\)-CDS problem, both in general graphs and in unit disk graphs.