A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
Author
Abstract
Suggested Citation
DOI: 10.1287/ijoc.2021.1106
Download full text from publisher
References listed on IDEAS
- Abilio Lucena & Nelson Maculan & Luidi Simonetti, 2010. "Reformulations and solution algorithms for the maximum leaf spanning tree problem," Computational Management Science, Springer, vol. 7(3), pages 289-311, July.
- Gao, Chao & Yao, Xin & Weise, Thomas & Li, Jinlong, 2015. "An efficient local search heuristic with row weighting for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 750-761.
- Edmund K. Burke & Yuri Bykov, 2016. "An Adaptive Flex-Deluge Approach to University Exam Timetabling," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 781-794, November.
- Anirudh Subramanyam & Panagiotis P. Repoussis & Chrysanthos E. Gounaris, 2020. "Robust Optimization of a Broad Class of Heterogeneous Vehicle Routing Problems Under Demand Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 661-681, July.
- 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.
- 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.
- 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.
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.- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Ciamac C. Moallemi & Utkarsh Patange, 2024. "Hybrid Scheduling with Mixed-Integer Programming at Columbia Business School," Interfaces, INFORMS, vol. 54(3), pages 222-240, May.
- Mats Carlsson & Sara Ceschia & Luca Gaspero & Rasmus Ørnstrup Mikkelsen & Andrea Schaerf & Thomas Jacob Riis Stidsen, 2023. "Exact and metaheuristic methods for a real-world examination timetabling problem," Journal of Scheduling, Springer, vol. 26(4), pages 353-367, August.
- Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
- Enrico Bartolini & Dominik Goeke & Michael Schneider & Mengdie Ye, 2021. "The Robust Traveling Salesman Problem with Time Windows Under Knapsack-Constrained Travel Time Uncertainty," Transportation Science, INFORMS, vol. 55(2), pages 371-394, March.
- Zhang, Yanzi & Diabat, Ali & Zhang, Zhi-Hai, 2021. "Reliable closed-loop supply chain design problem under facility-type-dependent probabilistic disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 180-209.
- Vic Grout, 2017. "A Simple Approach to Dynamic Optimisation of Flexible Optical Networks with Practical Application," Future Internet, MDPI, vol. 9(2), pages 1-11, May.
- Oleksandra Yezerska & Foad Mahdavi Pajouh & Alexander Veremyev & Sergiy Butenko, 2019. "Exact algorithms for the minimum s-club partitioning problem," Annals of Operations Research, Springer, vol. 276(1), pages 267-291, May.
- Wang, Yiyuan & Pan, Shiwei & Al-Shihabi, Sameh & Zhou, Junping & Yang, Nan & Yin, Minghao, 2021. "An improved configuration checking-based algorithm for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 294(2), pages 476-491.
- 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.
- Ceschia, Sara & Di Gaspero, Luca & Schaerf, Andrea, 2023. "Educational timetabling: Problems, benchmarks, and state-of-the-art results," European Journal of Operational Research, Elsevier, vol. 308(1), pages 1-18.
- Seizinger, Markus & Brunner, Jens O., 2023. "Optimized planning of nursing curricula in dual vocational schools focusing on the German health care system," European Journal of Operational Research, Elsevier, vol. 304(3), pages 1223-1241.
More about this item
Keywords
metaheuristic; minimum dominating set; vertex weighting; local search; search space reduction;All these keywords.
Statistics
Access and download statisticsCorrections
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:34:y:2022:i:2:p:817-833. 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.