A Simulated Annealing-Based Multiobjective Optimization Algorithm for Minimum Weight Minimum Connected Dominating Set Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910459007860736 |
|---|---|
| author | Dahmri, Hayet Bouamama, Salim |
| author_facet | Dahmri, Hayet Bouamama, Salim |
| contents | Minimum connected dominating set problem is an NP-hard combinatorial optimization problem in graph theory. Finding connected dominating set is of high interest in various domains such as wireless sensor networks, optical networks, and systems biology. Its weighted variant named minimum weight connected dominating set is also useful in such applications. In this paper, we propose a simulated annealing algorithm based on a greedy heuristic for tackling a variant of the minimum connected dominating set problem and that by exploiting two objectives together namely the cardinality and the total weight of the connected dominating set. Experimental results compared to those obtained by a recent proposed research show the superiority of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_11527 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Simulated Annealing-Based Multiobjective Optimization Algorithm for Minimum Weight Minimum Connected Dominating Set Problem Dahmri, Hayet Bouamama, Salim Artificial Intelligence Minimum connected dominating set problem is an NP-hard combinatorial optimization problem in graph theory. Finding connected dominating set is of high interest in various domains such as wireless sensor networks, optical networks, and systems biology. Its weighted variant named minimum weight connected dominating set is also useful in such applications. In this paper, we propose a simulated annealing algorithm based on a greedy heuristic for tackling a variant of the minimum connected dominating set problem and that by exploiting two objectives together namely the cardinality and the total weight of the connected dominating set. Experimental results compared to those obtained by a recent proposed research show the superiority of our approach. |
| title | A Simulated Annealing-Based Multiobjective Optimization Algorithm for Minimum Weight Minimum Connected Dominating Set Problem |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2312.11527 |