IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v7y2019i12p1173-d293555.html
   My bibliography  Save this article

Multi-Start Local Search Algorithm for the Minimum Connected Dominating Set Problems

Author

Listed:
  • Ruizhi Li

    (School of Computer Science and Technology, Jilin University, Changchun 130012, China
    School of Management Science and Information Engineering, Jilin University of Finance and Economics, Changchun 130117, China)

  • Shuli Hu

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China)

  • Huan Liu

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China)

  • Ruiting Li

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China)

  • Dantong Ouyang

    (School of Computer Science and Technology, Jilin University, Changchun 130012, China)

  • Minghao Yin

    (School of Computer Science and Information Technology, Northeast Normal University, Changchun 130024, China)

Abstract

The minimum connected dominating set (MCDS) problem is a very significant NP-hard combinatorial optimization problem, and it has been used in many fields such as wireless sensor networks and ad hoc networks. In this paper, we propose a novel multi-start local search algorithm (MSLS) to tackle the minimum connected dominating set problem. Firstly, we present the fitness mechanism to design the vertex score mechanism so that our algorithm can jump out of the local optimum. Secondly, we use the configuration checking (CC) mechanism to avoid the cycling problem. Then, we propose the vertex flipping mechanism to change the vertex state by combing the CC mechanism with the vertex score mechanism. Finally, we propose a multi-start local search framework based on these mechanisms. We compare the algorithm MSLS with other compared algorithms on extensive instances. The results of experiment show that MSLS is superior to other algorithms in solution quality and time efficiency on most instances.

Suggested Citation

  • Ruizhi Li & Shuli Hu & Huan Liu & Ruiting Li & Dantong Ouyang & Minghao Yin, 2019. "Multi-Start Local Search Algorithm for the Minimum Connected Dominating Set Problems," Mathematics, MDPI, vol. 7(12), pages 1-14, December.
    • Handle: RePEc:gam:jmathe:v:7:y:2019:i:12:p:1173-:d:293555
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/7/12/1173/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/7/12/1173/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Kelleher, Laura L. & Cozzens, Margaret B., 1988. "Dominating sets in social network graphs," Mathematical Social Sciences, Elsevier, vol. 16(3), pages 267-279, December.
    2. Bernard Gendron & Abilio Lucena & Alexandre Salles da Cunha & Luidi Simonetti, 2014. "Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 645-657, November.
    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. Xinyun Wu & Zhipeng Lü & Fred Glover, 2022. "A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 817-833, March.

    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. Adasme, Pablo & Andrade, Rafael Castro de, 2023. "Minimum weight clustered dominating tree problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 535-548.
    2. do Forte, Vinicius L. & Hanafi, Saïd & Lucena, Abilio, 2023. "Extended formulations for perfect domination problems and their algorithmic implications," European Journal of Operational Research, Elsevier, vol. 310(2), pages 566-581.
    3. Eduardo Álvarez-Miranda & Markus Sinnl, 2020. "A branch-and-cut algorithm for the maximum covering cycle problem," Annals of Operations Research, Springer, vol. 284(2), pages 487-499, January.
    4. Roshanaei, Vahid & Luong, Curtiss & Aleman, Dionne M. & Urbach, David R., 2020. "Reformulation, linearization, and decomposition techniques for balanced distributed operating room scheduling," Omega, Elsevier, vol. 93(C).
    5. 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.
    6. Roshanaei, Vahid & Naderi, Bahman, 2021. "Solving integrated operating room planning and scheduling: Logic-based Benders decomposition versus Branch-Price-and-Cut," European Journal of Operational Research, Elsevier, vol. 293(1), pages 65-78.
    7. Li, Xiangyong & Aneja, Y.P., 2017. "Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms," European Journal of Operational Research, Elsevier, vol. 257(1), pages 25-40.
    8. 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.
    9. Emiliano Alvarez & Juan Gabriel Brida & Pablo Mones, 2024. "On the Dynamics of Relative Prices and the Relationship with Inflation: An Empirical Approach," Computational Economics, Springer;Society for Computational Economics, vol. 63(1), pages 339-355, January.
    10. Xiangyong Li & Y. P. Aneja, 2020. "A new branch-and-cut approach for the generalized regenerator location problem," Annals of Operations Research, Springer, vol. 295(1), pages 229-255, December.
    11. Hamidreza Validi & Austin Buchanan, 2020. "The Optimal Design of Low-Latency Virtual Backbones," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 952-967, October.
    12. Balasundaram, Balabhaskar & Borrero, Juan S. & Pan, Hao, 2022. "Graph signatures: Identification and optimization," European Journal of Operational Research, Elsevier, vol. 296(3), pages 764-775.
    13. Yıldız, Barış & Karaşan, Oya Ekin, 2015. "Regenerator Location Problem and survivable extensions: A hub covering location perspective," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 32-55.
    14. Xinyun Wu & Zhipeng Lü & Fred Glover, 2022. "A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 817-833, March.
    15. Sourour Elloumi & Olivier Hudry & Estel Marie & Agathe Martin & Agnès Plateau & Stéphane Rovedakis, 2021. "Optimization of wireless sensor networks deployment with coverage and connectivity constraints," Annals of Operations Research, Springer, vol. 298(1), pages 183-206, March.
    16. Donghyun Kim & Deying Li & Omid Asgari & Yingshu Li & Alade O. Tokuta & Heekuck Oh, 2014. "Computing an effective decision making group of a society using social network analysis," Journal of Combinatorial Optimization, Springer, vol. 28(3), pages 577-587, October.
    17. Markus Leitner & Ivana Ljubić & Martin Riedler & Mario Ruthmair, 2019. "Exact Approaches for Network Design Problems with Relays," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 171-192, February.

    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:gam:jmathe:v:7:y:2019:i:12:p:1173-:d:293555. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.