Document Open Access Logo

Improving Local Search for Minimum Weighted Connected Dominating Set Problem by Inner-Layer Local Search

Authors Bohan Li , Kai Wang, Yiyuan Wang , Shaowei Cai

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.39.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Bohan Li
  • State Key Laboratory of Computer Science Institute of Software, Chinese Academy of Sciences, Beijing, China
  • School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China
Kai Wang
  • School of Computer Science and Information Technology, Northeast Normal University, Changchun, China
Yiyuan Wang
  • School of Computer Science and Information Technology, Northeast Normal University, Changchun, China
  • Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Chnagchun, China
Shaowei Cai
  • State Key Laboratory of Computer Science Institute of Software, Chinese Academy of Sciences, Beijing, China
  • School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing, China

Funding

This work is partially supported by National Key R&D Program of China (2019AAA0105200), Beijing Academy of Artificial Intelligence (BAAI), NSFC Grant 61806050, and Jilin Science and Technology Association QT202005.

Cite As Get BibTex

Bohan Li, Kai Wang, Yiyuan Wang, and Shaowei Cai. Improving Local Search for Minimum Weighted Connected Dominating Set Problem by Inner-Layer Local Search. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CP.2021.39

Abstract

The minimum weighted connected dominating set (MWCDS) problem is an important variant of connected dominating set problems with wide applications, especially in heterogenous networks and gene regulatory networks. In the paper, we develop a nested local search algorithm called NestedLS for solving MWCDS on classic benchmarks and massive graphs. In this local search framework, we propose two novel ideas to make it effective by utilizing previous search information. First, we design the restart based smoothing mechanism as a diversification method to escape from local optimal. Second, we propose a novel inner-layer local search method to enlarge the candidate removal set, which can be modelled as an optimized version of spanning tree problem. Moreover, inner-layer local search method is a general method for maintaining the connectivity constraint when dealing with massive graphs. Experimental results show that NestedLS outperforms state-of-the-art meta-heuristic algorithms on most instances.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomized local search
  • Applied computing → Operations research
Keywords
  • Operations Research
  • NP-hard Problem
  • Local Search
  • Weighted Connected Dominating Set Problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Jamal N Al-Karaki and Ahmed E Kamal. Efficient virtual-backbone routing in mobile ad hoc networks. Computer Networks, 52(2):327-350, 2008. Google Scholar
  2. Christoph Ambühl, Thomas Erlebach, Matúš Mihalák, and Marc Nunkesser. Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 3-14. Springer, 2006. Google Scholar
  3. Salim Bouamama, Christian Blum, and Jean-Guillaume Fages. An algorithm based on ant colony optimization for the minimum connected dominating set problem. Applied Soft Computing, 80:672-686, 2019. Google Scholar
  4. Shaowei Cai and Kaile Su. Local search for boolean satisfiability with configuration checking and subscore. Artif. Intell., 204:75-98, 2013. Google Scholar
  5. Orhan Dagdeviren, Kayhan Erciyes, and Savio Tse. Semi-asynchronous and distributed weighted connected dominating set algorithms for wireless sensor networks. Computer Standards & Interfaces, 42:143-156, 2015. Google Scholar
  6. Zuleyha Akusta Dagdeviren, Dogan Aydin, and Muhammed Cinsdikici. Two population-based optimization algorithms for minimum weight connected dominating set problem. Appl. Soft Comput., 59:644-658, 2017. Google Scholar
  7. Tetsuya Fujie. An exact algorithm for the maximum leaf spanning tree problem. Computers & Operations Research, 30(13):1931-1944, 2003. Google Scholar
  8. Fred Glover, Manuel Laguna, et al. Handbook of combinatorial optimization. Springer, pages 2093-2229, 1998. Google Scholar
  9. Sudipto Guha and Samir Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374-387, 1998. Google Scholar
  10. John Hopcroft and Robert Tarjan. Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6):372-378, 1973. Google Scholar
  11. Raka Jovanovic and Milan Tuba. Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. Computer Science and Information Systems, 10(1):133-149, 2013. Google Scholar
  12. Michael Levandowsky and David Winter. Distance between sets. Nature, 234(5323):34-35, 1971. Google Scholar
  13. Bohan Li, Xindi Zhang, Shaowei Cai, Jinkun Lin, Yiyuan Wang, and Christian Blum. Nucds: An efficient local search algorithm for minimum connected dominating set. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, pages 1503-1510, 2020. Google Scholar
  14. Jiawei Li, Xiangxi Wen, Minggong Wu, Fei Liu, and Shuangfeng Li. Identification of key nodes and vital edges in aviation network based on minimum connected dominating set. Physica A: Statistical Mechanics and its Applications, 541:123340, 2020. Google Scholar
  15. Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Mauro Birattari, and Thomas Stützle. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43-58, 2016. Google Scholar
  16. Tijana Milenković, Vesna Memišević, Anthony Bonato, and Nataša Pržulj. Dominating biological networks. PloS one, 6(8):e23016, 2011. Google Scholar
  17. Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. In Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 4292-4293, 2015. Google Scholar
  18. Lu Ruan, Hongwei Du, Xiaohua Jia, Weili Wu, Yingshu Li, and Ker-I Ko. A greedy approximation for minimum connected dominating sets. Theoretical Computer Science, 329(1-3):325-330, 2004. Google Scholar
  19. Shyong Jian Shyu, Peng-Yeng Yin, and Bertrand MT Lin. An ant colony optimization algorithm for the minimum weight vertex cover problem. Annals of Operations Research, 131(1-4):283-304, 2004. Google Scholar
  20. John Thornton, Duc Nghia Pham, Stuart Bain, and Valnir Ferreira Jr. Additive versus multiplicative clause weighting for sat. In AAAI, volume 4, pages 191-196, 2004. Google Scholar
  21. Mustafa Tosun and Elif Haytaoglu. A new distributed weighted connected dominating set algorithm for wsns. In 2018 IEEE 8th International Conference on Consumer Electronics-Berlin (ICCE-Berlin), pages 1-6. IEEE, 2018. Google Scholar
  22. Sattar Vakili and Qing Zhao. Distributed node-weighted connected dominating set problems. In 2013 Asilomar Conference on Signals, Systems and Computers, pages 238-241, 2013. Google Scholar
  23. Dingding Wang, Tao Li, and Mitsunori Ogihara. Generating pictorial storylines via minimum-weight connected dominating set approximation in multi-view graphs. In Twenty-Sixth AAAI Conference on Artificial Intelligence, pages 683-689, 2012. Google Scholar
  24. Yiyuan Wang, Shaowei Cai, Jiejiang Chen, and Minghao Yin. A fast local search algorithm for minimum weight dominating set problem on massive graphs. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 1514-1522, 2018. Google Scholar
  25. Yiyuan Wang, Shaowei Cai, Jiejiang Chen, and Minghao Yin. Sccwalk: An efficient local search algorithm and its improvements for maximum weight clique problem. Artificial Intelligence, 280:103230, 2020. Google Scholar
  26. Yiyuan Wang, Shaowei Cai, and Minghao Yin. Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function. Journal of Artificial Intelligence Research, 58:267-295, 2017. Google Scholar
  27. Yu Wang, Weizhao Wang, and Xiang-Yang Li. Efficient distributed low-cost backbone formation for wireless networks. IEEE Transactions on Parallel and Distributed Systems, 17(7):681-693, 2006. Google Scholar
  28. Yu Wang, Weizhao Wang, and Xiang-Yang Li. Weighted Connected Dominating Set, pages 1020-1023. Springer US, 2008. Google Scholar
  29. Feng Zou, Yuexuan Wang, XiaoHua Xu, Xianyue Li, Hongwei Du, Peng-Jun Wan, and Weili Wu. New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theor. Comput. Sci., 412(3):198-208, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact