The minimum weight dominating set (MWDS) problem in massive graphs / Ichrak Messah

Public ISBD Titre : The minimum weight dominating set (MWDS) problem in massive graphs Type de document : texte imprimé Auteurs : Ichrak Messah, Auteur ; Isra Lamari ; Samir Balbal, Directeur de thèse Editeur : Setif:UFA Année de publication : 2024 Importance : 1 vol (64 f .) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Graph Optimization Heuristic methods Metaheuristics Minimum weight dominating set Deep optimization Massive graph Greedy algorithm Index. décimale : 004 - Informatique Résumé : An important generalization of the Minimum Dominating Set (MDS) problem which is known to be NP-hard with extensive applications; The Minimum Weight Dominating Set (MWDS) problem is the minimum number of vertices in the dominating set with minimum total weight. In general we staged a dominant set is generated by a greedy algorithm, Extensive experiments based on five popular benchmarks of different scales are carried out to evaluate the proposed algorithm. Compared to five state-of-the-art heuristic algorithms, DeepOpt-MWDS performs better on random and classic benchmarks and obtains the best solutions on almost all massive graphs. So, we adapt the proposed general framework DeepOpt to NP-hard problem to verify its generality and achieve good performance. Note de contenu : Sommaire Dedicates ......................................................................................... Erreur ! Signet non défini. Thanks ..................................................................................................................................... IV Résume ..................................................................................................................................... V Abstract ................................................................................................................................... VI General Introduction ................................................................................................................ 11 CHAPTER 01 Graph theory and dominant set ........................................................................ 13 1.1 Introduction .................................................................................................................... 14 1.2 Graph theory ................................................................................................................... 14 1.2.1 Basics ...................................................................................................................... 14 1.2.2 Terminologies ........................................................................................................ 16 1.3 Structural representation of graphs ............................................................................... 17 1.3.1 Representation by Matrix ........................................................................................ 18 1.3.2 Representation by list ............................................................................................. 20 1.4 Dominating sets ............................................................................................................. 21 1.4.1 Minimal dominating set (MDS) ............................................................................. 21 1.4.2 Minimal weight dominating set (MWDS) ............................................................. 21 1.5 Conclusion ..................................................................................................................... 22 CHAPTER 02 Problem solving method .................................................................................. 24 2.1 Introduction ................................................................................................................... 25 2.2 The Optimization Combination Problem………………………………………………... 25 2.2.1 Complex elements .................................................................................................. 26 2.3.2 Complexity Classes ................................................................................................ 28 2.4 Optimization methods ................................................................................................... 31 2.4.1 Classification of methods ....................................................................................... 31 2.4.1.1 Exact methods .............................................................................................. 32 2.4.1.2 Approximate methods .................................................................................. 34 2.5 Conclusion ..................................................................................................................... 40 CHAPTER 03 Contributions and results ................................................................................. 41 3.1 Introduction .................................................................................................................... 42 3.2 Contribution .................................................................................................................. 42 3.2.1 Minimal Dominating Set (MDS) ............................................................................ 42 3.2.1.2 Example that exemplifies MDS .......................................................................... 44 3.2.2 Minimal Weight Dominating Set (MWDS) ............................................................ 46 3.3 Data set ........................................................................................................................... 48 3.3.1 The benchmarks ...................................................................................................... 48 3.3.2 Presentation of instance .......................................................................................... 49 3.4 Development environment ............................................................................................. 51 3.5 Evaluation of our heuristic evaluation for MWDS and MDS ........................................ 51 3.5.1 Evaluation of our MWDS and MDS approach for (The benchmark) .................... 51 3.6 DISCUSSION ............................................................................................................... 58 3.7 Conclusion ..................................................................................................................... 59 General Conclusion .................................................................................................................. 60 Côte titre : MAI/0902 The minimum weight dominating set (MWDS) problem in massive graphs [texte imprimé] / Ichrak Messah, Auteur ; Isra Lamari ; Samir Balbal, Directeur de thèse . - [S.l.] : Setif:UFA, 2024 . - 1 vol (64 f .) ; 29 cm. Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Graph Optimization Heuristic methods Metaheuristics Minimum weight dominating set Deep optimization Massive graph Greedy algorithm Index. décimale : 004 - Informatique Résumé : An important generalization of the Minimum Dominating Set (MDS) problem which is known to be NP-hard with extensive applications; The Minimum Weight Dominating Set (MWDS) problem is the minimum number of vertices in the dominating set with minimum total weight. In general we staged a dominant set is generated by a greedy algorithm, Extensive experiments based on five popular benchmarks of different scales are carried out to evaluate the proposed algorithm. Compared to five state-of-the-art heuristic algorithms, DeepOpt-MWDS performs better on random and classic benchmarks and obtains the best solutions on almost all massive graphs. So, we adapt the proposed general framework DeepOpt to NP-hard problem to verify its generality and achieve good performance. Note de contenu : Sommaire Dedicates ......................................................................................... Erreur ! Signet non défini. Thanks ..................................................................................................................................... IV Résume ..................................................................................................................................... V Abstract ................................................................................................................................... VI General Introduction ................................................................................................................ 11 CHAPTER 01 Graph theory and dominant set ........................................................................ 13 1.1 Introduction .................................................................................................................... 14 1.2 Graph theory ................................................................................................................... 14 1.2.1 Basics ...................................................................................................................... 14 1.2.2 Terminologies ........................................................................................................ 16 1.3 Structural representation of graphs ............................................................................... 17 1.3.1 Representation by Matrix ........................................................................................ 18 1.3.2 Representation by list ............................................................................................. 20 1.4 Dominating sets ............................................................................................................. 21 1.4.1 Minimal dominating set (MDS) ............................................................................. 21 1.4.2 Minimal weight dominating set (MWDS) ............................................................. 21 1.5 Conclusion ..................................................................................................................... 22 CHAPTER 02 Problem solving method .................................................................................. 24 2.1 Introduction ................................................................................................................... 25 2.2 The Optimization Combination Problem………………………………………………... 25 2.2.1 Complex elements .................................................................................................. 26 2.3.2 Complexity Classes ................................................................................................ 28 2.4 Optimization methods ................................................................................................... 31 2.4.1 Classification of methods ....................................................................................... 31 2.4.1.1 Exact methods .............................................................................................. 32 2.4.1.2 Approximate methods .................................................................................. 34 2.5 Conclusion ..................................................................................................................... 40 CHAPTER 03 Contributions and results ................................................................................. 41 3.1 Introduction .................................................................................................................... 42 3.2 Contribution .................................................................................................................. 42 3.2.1 Minimal Dominating Set (MDS) ............................................................................ 42 3.2.1.2 Example that exemplifies MDS .......................................................................... 44 3.2.2 Minimal Weight Dominating Set (MWDS) ............................................................ 46 3.3 Data set ........................................................................................................................... 48 3.3.1 The benchmarks ...................................................................................................... 48 3.3.2 Presentation of instance .......................................................................................... 49 3.4 Development environment ............................................................................................. 51 3.5 Evaluation of our heuristic evaluation for MWDS and MDS ........................................ 51 3.5.1 Evaluation of our MWDS and MDS approach for (The benchmark) .................... 51 3.6 DISCUSSION ............................................................................................................... 58 3.7 Conclusion ..................................................................................................................... 59 General Conclusion .................................................................................................................. 60 Côte titre : MAI/0902

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
MAI/0902	MAI/0902	Mémoire	Bibliothéque des sciences	Anglais	Disponible Disponible

---

1 (1 - 1 / 1)