A Greedy Simulated Annealing-based Multiobjective Algorithm for the Minimum Weight Minimum Connected Dominating Set Problem

Authors

  • Hayet Dahmri Mechatronics Laboratory (LMETR), Optics and Precision Mechanics Institute, University Setif 1 - Ferhat Abbas, Setif, 19000, Algeria | Department of Computer Science, University Setif 1 - Ferhat Abbas, Setif, 19000, Algeria
  • Salim Bouamama Mechatronics Laboratory (LMETR), Optics and Precision Mechanics Institute, University Setif 1 - Ferhat Abbas, Setif, 19000, Algeria | Department of Computer Science, University Setif 1 - Ferhat Abbas, Setif, 19000, Algeria
  • Samir Balbal Department of Computer Science, University Setif 1 - Ferhat Abbas, Setif, 19000, Algeria
Volume: 14 | Issue: 5 | Pages: 16686-16691 | October 2024 | https://doi.org/10.48084/etasr.8272

Abstract

The minimum connected dominating set problem is a well-known NP-hard combinatorial optimization problem in graph theory, with various fields of application including wireless sensor networks, optical networks, and systems biology. This paper presents an adaptive multiobjective simulated annealing approach to address a variant of the minimum connected dominating set problem known as the Minimum Weight Minimum Connected Dominating Set Problem. This approach combines a multiobjective Pareto set with a greedy simulated annealing algorithm to tackle the problem by simultaneously optimizing two objectives, namely the cardinality and the total weight of the connected dominating set. Experimental results compared to those obtained by current state-of-the-art approaches show the superiority of our method.

Keywords:

greedy heuristic, Pareto optimality, minimum connected dominating set, minimum weight connected dominating set, simulated annealing

Downloads

Download data is not yet available.

References

Y. Wang, W. Wang, and X.-Y. Li, "Distributed low-cost backbone formation for wireless ad hoc networks," in 6th ACM International Symposium on Mobile ad Hoc Networking and Computing, Urbana, IL , USA, Dec. 2005, pp. 2–13.

J. Zhang and C.-F. Jia, "Minimum Connected Dominating Set Algorithm with Weight in Wireless Sensor Networks," in 4th International Conference on Wireless Communications, Networking and Mobile Computing, Dalian, China, Oct. 2008, pp. 1–4.

R. Misra and C. Mandal, "Minimum Connected Dominating Set Using a Collaborative Cover Heuristic for Ad Hoc Sensor Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 3, pp. 292–302, Mar. 2010.

A. Sen, S. Banerjee, P. Ghosh, S. Murthy, and H. Ngo, "Brief announcement: on regenerator placement problems in optical networks," in 22nd ACM Symposium on Parallelism in Algorithms and Architectures, Thira, Greece, Jun. 2010, pp. 178–180.

A. Sen, S. Murthy, and S. Bandyopadhyay, "On Sparse Placement of Regenerator Nodes in Translucent Optical Network," in IEEE GLOBECOM 2008 - 2008 IEEE Global Telecommunications Conference, New Orleans, LA, USA, Dec. 2008, pp. 1–6.

T. Milenkovic, V. Memisevic, A. Bonato, and N. Przulj, "Dominating Biological Networks," PLOS ONE, vol. 6, no. 8, Jul. 2011, Art. no. e23016.

J. Blum, M. Ding, A. Thaeler, and X. Cheng, "Connected Dominating Set in Sensor Networks and MANETs," in Handbook of Combinatorial Optimization: Supplement Volume B, D.-Z. Du and P. M. Pardalos, Eds. Boston, MA, USA: Springer, 2005, pp. 329–369.

D.-Z. Du and P.-J. Wan, Connected Dominating Set: Theory and Applications. New York, NY, USA: Springer, 2012.

D. S. Johnson and M. R. Garey, "A guide to the theory of NP-completeness," The Journal of Symbolic Logic, vol. 48, no. 2, pp. 498–500, Jun. 1983.

M. Morgan and V. Grout, "Metaheuristics for Wireless Network Optimisation," in The Third Advanced International Conference on Telecommunications, Morne, Mauritius, Dec. 2007, pp. 15–15.

R. Jovanovic and M. Tuba, "Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem," Computer Science and Information Systems, vol. 10, no. 1, pp. 133–149, 2013.

R. Li, S. Hu, J. Gao, Y. Zhou, Y. Wang, and M. Yin, "GRASP for connected dominating set problems," Neural Computing and Applications, vol. 28, no. 1, pp. 1059–1067, Dec. 2017.

X. Wu, Z. Lu, and P. Galinier, "Restricted swap-based neighborhood search for the minimum connected dominating set problem," Networks, vol. 69, no. 2, pp. 222–236, 2017.

A.-R. Hedar, R. Ismail, G. A. El-Sayed, and K. M. J. Khayyat, "Two Meta-Heuristics Designed to Solve the Minimum Connected Dominating Set Problem for Wireless Networks Design and Management," Journal of Network and Systems Management, vol. 27, no. 3, pp. 647–687, Jul. 2019.

Z. A. Dagdeviren, D. Aydin, and M. Cinsdikici, "Two population-based optimization algorithms for minimum weight connected dominating set problem," Applied Soft Computing, vol. 59, pp. 644–658, Oct. 2017.

S. Bouamama, C. Blum, and J.-G. Fages, "An algorithm based on ant colony optimization for the minimum connected dominating set problem," Applied Soft Computing, vol. 80, pp. 672–686, Jul. 2019.

D. Rengaswamy, S. Datta, and S. Ramalingam, "Multiobjective Genetic Algorithm for Minimum Weight Minimum Connected Dominating Set," in International Conference on Intelligent Systems Design and Applications, Delhi, India, Dec. 2017, pp. 558–567.

H. Dahmri and S. Bouamama, "Improved NSGA-II for Minimum Weight Minimum Connected Dominating Set Problem," in International Symposium on Modelling and Implementation of Complex Systems, Batna, Algeria, Oct. 2020, pp. 248–261.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, no. 4598, pp. 671–680, May 1983.

M. O. Genc and N. Kaya, "Vibration Damping Optimization using Simulated Annealing Algorithm for Vehicle Powertrain System," Engineering, Technology & Applied Science Research, vol. 10, no. 1, pp. 5164–5167, Feb. 2020.

S. F. Sesay, C. W. Wekesa, and L. M. H. Ngoo, "Optimal Placement of Superconducting Magnetic Energy Storages in a Distribution Network with Embedded Wind Power Generation," Engineering, Technology & Applied Science Research, vol. 14, no. 2, pp. 13416–13424, Apr. 2024.

N. T. Linh and P. V. Long, "A Novel Solution Method for the Distribution Network Reconfiguration Problem based on an Objective Function and considering the Cost of Electricity Transmission," Engineering, Technology & Applied Science Research, vol. 13, no. 6, pp. 12366–12372, Dec. 2023.

A. Suppapitnarm, K. A. Seffen, G. T. Parks, and P. J. Clarkson, "A Simulated Annealing Algorithm for Multiobjective Optimization," Engineering Optimization, vol. 33, no. 1, pp. 59–85, Nov. 2000.

F. Romeo, A. K. Sangiovanni Vincentelli, and M. D. Huang, "An Efficient General Cooling Schedule for Simulated Annealing," in Proceedings of IEEE International Conference on Computer Aided Design, Jan. 1986, pp. 381–384.

M. Nazarieh, A. Wiese, T. Will, M. Hamed, and V. Helms, "Identification of key player genes in gene regulatory networks," BMC Systems Biology, vol. 10, no. 1, Sep. 2016, Art. no. 88.

E. Zitzler and L. Thiele, "Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach," IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257–271, Aug. 1999.

Downloads

How to Cite

[1]
Dahmri, H., Bouamama, S. and Balbal, S. 2024. A Greedy Simulated Annealing-based Multiobjective Algorithm for the Minimum Weight Minimum Connected Dominating Set Problem. Engineering, Technology & Applied Science Research. 14, 5 (Oct. 2024), 16686–16691. DOI:https://doi.org/10.48084/etasr.8272.

Metrics

Abstract Views: 107
PDF Downloads: 103

Metrics Information