IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v30y2018i2p217-224.html
   My bibliography  Save this article

Computing Minimum k -Connected m -Fold Dominating Set in General Graphs

Author

Listed:
  • Zhao Zhang

    (College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, China)

  • Jiao Zhou

    (College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, China)

  • Shaojie Tang

    (Naveen Jindal School of Management, University of Texas at Dallas, Richardson, Texas 75080)

  • Xiaohui Huang

    (College of Mathematics Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, China)

  • Ding-Zhu Du

    (Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75080)

Abstract

Connected dominating set (CDS) problem has been extensively studied in the literature due to its applications in many domains, including computer science and operations research. For example, CDS has been recommended to serve as a virtual backbone in wireless sensor networks (WSNs). Since sensor nodes in WSNs are prone to failures, it is important to build a fault-tolerant virtual backbone that maintains a certain degree of redundancy. A fault-tolerant virtual backbone can be modeled as a k -connected m -fold dominating set ( k , m )-CDS. For a connected graph G = ( V , E ) and two fixed integers k and m , a node set C ⊆ V is a ( k , m )-CDS of G if every node in V \ C has at least m neighbors in C , and the subgraph of G induced by C is k -connected. Previous to this work, approximation algorithms with guaranteed performance ratio in a general graph were known only for k ≤ 3. This paper makes significant progress by presenting a (2 k − 1) α 0 approximation algorithm for general k and m with m ≥ k , where α 0 is the performance ratio for the minimum (1, m )-CDS problem. Using a currently best-known ratio for α 0 , our algorithm has performance ratio O (lnΔ), where Δ is the maximum degree of the graph. Simulation results validate the effectiveness of our algorithm.

Suggested Citation

  • Zhao Zhang & Jiao Zhou & Shaojie Tang & Xiaohui Huang & Ding-Zhu Du, 2018. "Computing Minimum k -Connected m -Fold Dominating Set in General Graphs," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 217-224, May.
    • Handle: RePEc:inm:orijoc:v:30:y:2018:i:2:p:217-224
    DOI: 10.1287/ijoc.2017.0776
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2017.0776
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2017.0776?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Jiao Zhou & Zhao Zhang & Weili Wu & Kai Xing, 2014. "A greedy algorithm for the fault-tolerant connected dominating set in a general graph," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 310-319, July.
    2. M. Gisela Bardossy & S. Raghavan, 2010. "Dual-Based Local Search for the Connected Facility Location and Related Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 584-602, November.
    3. Weiping Shang & Frances Yao & Pengjun Wan & Xiaodong Hu, 2008. "On minimum m-connected k-dominating set problem in unit disc graphs," Journal of Combinatorial Optimization, Springer, vol. 16(2), pages 99-106, August.
    4. Yishuo Shi & Yaping Zhang & Zhao Zhang & Weili Wu, 2016. "A greedy algorithm for the minimum $$2$$ 2 -connected $$m$$ m -fold dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 31(1), pages 136-151, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Xiaozhi Wang & Xianyue Li & Bo Hou & Wen Liu & Lidong Wu & Suogang Gao, 2021. "A greedy algorithm for the fault-tolerant outer-connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 118-127, January.
    2. Yaoyao Zhang & Zhao Zhang & Ding-Zhu Du, 2023. "Construction of minimum edge-fault tolerant connected dominating set in a general graph," Journal of Combinatorial Optimization, Springer, vol. 45(2), pages 1-12, March.
    3. Zhao Zhang & Wei Liang & Hongmin W. Du & Siwen Liu, 2022. "Constant Approximation for the Lifetime Scheduling Problem of p -Percent Coverage," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2675-2685, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jiao Zhou & Zhao Zhang & Shaojie Tang & Xiaohui Huang & Ding-Zhu Du, 2018. "Breaking the O (ln n ) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 225-235, May.
    2. Yaoyao Zhang & Zhao Zhang & Ding-Zhu Du, 2023. "Construction of minimum edge-fault tolerant connected dominating set in a general graph," Journal of Combinatorial Optimization, Springer, vol. 45(2), pages 1-12, March.
    3. Xiaozhi Wang & Xianyue Li & Bo Hou & Wen Liu & Lidong Wu & Suogang Gao, 2021. "A greedy algorithm for the fault-tolerant outer-connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 118-127, January.
    4. Yanhong Gao & Ping Li & Xueliang Li, 2022. "Further results on the total monochromatic connectivity of graphs," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 603-616, August.
    5. Yishuo Shi & Yaping Zhang & Zhao Zhang & Weili Wu, 2016. "A greedy algorithm for the minimum $$2$$ 2 -connected $$m$$ m -fold dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 31(1), pages 136-151, January.
    6. Tian Liu & Zhao Lu & Ke Xu, 2015. "Tractable connected domination for restricted bipartite graphs," Journal of Combinatorial Optimization, Springer, vol. 29(1), pages 247-256, January.
    7. Chen Liao & Shiyan Hu, 2010. "Polynomial time approximation schemes for minimum disk cover problems," Journal of Combinatorial Optimization, Springer, vol. 20(4), pages 399-412, November.
    8. Kejia Zhang & Qilong Han & Guisheng Yin & Haiwei Pan, 2016. "OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1623-1641, May.
    9. Dong Liang & Wilbert E. Wilhelm, 2013. "Dual‐ascent and primal heuristics for production‐assembly‐distribution system design," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 1-18, February.
    10. Korsnes, Reinert, 2010. "Rapid self-organised initiation of ad hoc sensor networks close above the percolation threshold," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(14), pages 2841-2848.
    11. Contreras, Ivan & Fernández, Elena, 2012. "General network design: A unified view of combined location and network design problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 680-697.
    12. Stefan Gollowitzer & Bernard Gendron & Ivana Ljubić, 2013. "A cutting plane algorithm for the Capacitated Connected Facility Location Problem," Computational Optimization and Applications, Springer, vol. 55(3), pages 647-674, July.
    13. Li, Gang & Balakrishnan, Anantaram, 2016. "Models and algorithms for network reduction," European Journal of Operational Research, Elsevier, vol. 248(3), pages 930-942.
    14. Austin Buchanan & Je Sang Sung & Sergiy Butenko & Eduardo L. Pasiliao, 2015. "An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 178-188, February.
    15. Wei Ding & Ke Qiu, 2018. "A quadratic time exact algorithm for continuous connected 2-facility location problem in trees," Journal of Combinatorial Optimization, Springer, vol. 36(4), pages 1262-1298, November.
    16. Jiao Zhou & Zhao Zhang & Weili Wu & Kai Xing, 2014. "A greedy algorithm for the fault-tolerant connected dominating set in a general graph," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 310-319, July.
    17. Kuzbakov, Yerlan & Ljubić, Ivana, 2024. "New formulations for two location problems with interconnected facilities," European Journal of Operational Research, Elsevier, vol. 314(1), pages 51-65.
    18. Jing Gao & Jianzhong Li & Yingshu Li, 2016. "Approximate event detection over multi-modal sensing data," Journal of Combinatorial Optimization, Springer, vol. 32(4), pages 1002-1016, November.
    19. Mao Luo & Huigang Qin & Xinyun Wu & Caiquan Xiong, 2024. "A novel local search approach with connected dominating degree-based incremental neighborhood evaluation for the minimum 2-connected dominating set problem," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-26, July.
    20. Yaoyao Zhang & Chaojie Zhu & Shaojie Tang & Yingli Ran & Ding-Zhu Du & Zhao Zhang, 2024. "Evolutionary Algorithm on General Cover with Theoretically Guaranteed Approximation Ratio," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 510-525, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:30:y:2018:i:2:p:217-224. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.