University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Samir Balbal |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheApproche Heuristique pour Le Problème De L’ensemble Dominant à Poids Minimal Dans Les Graphes Orientés / Rihab Aissa
Titre : Approche Heuristique pour Le Problème De L’ensemble Dominant à Poids Minimal Dans Les Graphes Orientés Type de document : document électronique Auteurs : Rihab Aissa, Auteur ; Chaima Cherfouh, Auteur ; Samir Balbal, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2024 Importance : 1 vol (69 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : L’ensemble dominant minimal
Heuristiques
Sommets
Graphe orienté
Algorithme gloutonIndex. décimale : 004 Informatique Résumé :
Il existe de nombreuses approches heuristiques et exactes dans la littérature pour résoudre
le problème de l’ensemble dominant de poids minimum (MWDS) sur les graphes non
orientés pondérés par les sommets, qui est un problème NP-difficile bien connu. Cependant,
peu d’attention a été accordée à son équivalent dans les graphes orientés pondérés
par les sommets, appelé problème de l’ensemble dominant de poids minimum dans les
graphes orientés (MWDDS). Le problème de l’ensemble dominant orienté à poids minimal
(MWDDS) cherche un ensemble dominant orienté avec la somme minimale des poids
des noeuds qui le composent Il s’agit d’un problème d’optimisation combinatoire N Pdifficile
qui trouve des applications dans la modélisation d’une grande variété d’interactions
dirigées dans des réseaux hétérogènes complexes comme la réaction chimique, la
régulation métabolique, la propagation d’une maladie infectieuse.
Dans ce sujet, nous voulons explorer les méthodes heuristiques pour résoudre ce problème
MWDDS des graphes. On a appliquer une technique puis la comparer aux approches
trouvées dans la littérature. L’objectif est de comprendre le problème MWDDS, proposer
des solutions heuristiques, et comparer leurs performances aux méthodes établies.
En conclusion, les approches heuristiques offrent un bon compromis entre qualité des solutions
et efficacité computationnelle pour le problème de l’ensemble dominant à poids
minimal dans les graphes orientés, faisant d’elles des outils précieux pour la résolution de
problèmes complexes en temps limité.Note de contenu : Sommaire
1 Théorie des graphes et les ensembles dominants 9
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Qu’est-ce qu’un graphe ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Notion de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.1 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.2 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Représentation structurelle des graphes . . . . . . . . . . . . . . . . . . . 5
1.4.1 Représentation structurelle d’un graphe non orienté . . . . . . . . . 5
1.4.2 Représentation structurelle d’un graphe orienté . . . . . . . . . . . 7
1.5 Les ensembles dominants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Exemple illustratif d’un ensemble dominant . . . . . . . . . . . . . 9
1.6 Ensemble minimal dominant MDS . . . . . . . . . . . . . . . . . . . . . . 9
1.6.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.2 Exemple illustratif d’un ensemble dominant minimal . . . . . . . . 10
1.7 Ensemble dominant dirigé à poids minimal(MWDDS) . . . . . . . . . . . . 10
1.7.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7.2 Exemple illustratif d’un ensemble dominant dirigé à poids minimal 11
1.7.3 Formalisation mathématique . . . . . . . . . . . . . . . . . . . . . 11
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Optimisation combinatoire 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Le probléme d’optimisation combinatoire . . . . . . . . . . . . . . . . . . . 14
2.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Elément de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Notion de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Les méthodes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 Les méthodes Approchées . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Contributions et résultats 26
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Algorithme de problème MWDDS . . . . . . . . . . . . . . . . . . . 27
3.2.2 Exemple illustratif pour MWDDS . . . . . . . . . . . . . . . . . . . 32
3.3 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . . 36
3.4 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 Résultats et discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.1 Résultats pour Type 1 . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.2 Résultats pour Type 2 . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5.3 Résultats pour UDG . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Côte titre : MAI/0941 Approche Heuristique pour Le Problème De L’ensemble Dominant à Poids Minimal Dans Les Graphes Orientés [document électronique] / Rihab Aissa, Auteur ; Chaima Cherfouh, Auteur ; Samir Balbal, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2024 . - 1 vol (69 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : L’ensemble dominant minimal
Heuristiques
Sommets
Graphe orienté
Algorithme gloutonIndex. décimale : 004 Informatique Résumé :
Il existe de nombreuses approches heuristiques et exactes dans la littérature pour résoudre
le problème de l’ensemble dominant de poids minimum (MWDS) sur les graphes non
orientés pondérés par les sommets, qui est un problème NP-difficile bien connu. Cependant,
peu d’attention a été accordée à son équivalent dans les graphes orientés pondérés
par les sommets, appelé problème de l’ensemble dominant de poids minimum dans les
graphes orientés (MWDDS). Le problème de l’ensemble dominant orienté à poids minimal
(MWDDS) cherche un ensemble dominant orienté avec la somme minimale des poids
des noeuds qui le composent Il s’agit d’un problème d’optimisation combinatoire N Pdifficile
qui trouve des applications dans la modélisation d’une grande variété d’interactions
dirigées dans des réseaux hétérogènes complexes comme la réaction chimique, la
régulation métabolique, la propagation d’une maladie infectieuse.
Dans ce sujet, nous voulons explorer les méthodes heuristiques pour résoudre ce problème
MWDDS des graphes. On a appliquer une technique puis la comparer aux approches
trouvées dans la littérature. L’objectif est de comprendre le problème MWDDS, proposer
des solutions heuristiques, et comparer leurs performances aux méthodes établies.
En conclusion, les approches heuristiques offrent un bon compromis entre qualité des solutions
et efficacité computationnelle pour le problème de l’ensemble dominant à poids
minimal dans les graphes orientés, faisant d’elles des outils précieux pour la résolution de
problèmes complexes en temps limité.Note de contenu : Sommaire
1 Théorie des graphes et les ensembles dominants 9
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Qu’est-ce qu’un graphe ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Notion de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.1 Graphe non orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.2 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Représentation structurelle des graphes . . . . . . . . . . . . . . . . . . . 5
1.4.1 Représentation structurelle d’un graphe non orienté . . . . . . . . . 5
1.4.2 Représentation structurelle d’un graphe orienté . . . . . . . . . . . 7
1.5 Les ensembles dominants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Exemple illustratif d’un ensemble dominant . . . . . . . . . . . . . 9
1.6 Ensemble minimal dominant MDS . . . . . . . . . . . . . . . . . . . . . . 9
1.6.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.2 Exemple illustratif d’un ensemble dominant minimal . . . . . . . . 10
1.7 Ensemble dominant dirigé à poids minimal(MWDDS) . . . . . . . . . . . . 10
1.7.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7.2 Exemple illustratif d’un ensemble dominant dirigé à poids minimal 11
1.7.3 Formalisation mathématique . . . . . . . . . . . . . . . . . . . . . 11
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Optimisation combinatoire 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Le probléme d’optimisation combinatoire . . . . . . . . . . . . . . . . . . . 14
2.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Elément de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Notion de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Les méthodes d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.1 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.2 Les méthodes Approchées . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Contributions et résultats 26
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Algorithme de problème MWDDS . . . . . . . . . . . . . . . . . . . 27
3.2.2 Exemple illustratif pour MWDDS . . . . . . . . . . . . . . . . . . . 32
3.3 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . . 36
3.4 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 Résultats et discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.1 Résultats pour Type 1 . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.2 Résultats pour Type 2 . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5.3 Résultats pour UDG . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Côte titre : MAI/0941 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0941 MAI/0941 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Placement de services de sécurité dans l’IoT Type de document : texte imprimé Auteurs : Younes Abid, Auteur ; Layachi-Houssem Bendana, Auteur ; Samir Balbal, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2023 Importance : 1 vol (67 f .) Format : 29cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Internet des Objets
Ensemble dominant minimalIndex. décimale : 004 Informatique Résumé : L’émergence de l’Internet des objets (IoT) a suscité un intérêt croissant dans notre
société, en permettant la connectivité d’un large éventail d’objets, des plus petits aux plus
grands. Cependant, la sécurité représente un défi majeur dans le domaine de l’IoT, étant
donné le nombre massif d’appareils connectés et les données sensibles qui circulent sur
les réseaux. Assurer la protection de ces informations contre les cyberattaques revêt une
importance capitale. Dans ce contexte, le placement optimal des services de sécurité dans
l’IoT joue un rôle crucial pour garantir la sécurité des appareils et des données. Une approche
prometteuse pour optimiser ce placement est l’utilisation de l’ensemble dominant
minimal (MDS) dans les graphes, permettant d’optimiser l’allocation des ressources de
sécurité. Cependant, le problème de l’ensemble dominant minimal est considéré comme
NP-difficile, rendant sa résolution complexe. Ainsi, l’objectif de cette étude est d’explorer
l’utilisation de méthodes heuristiques et métaheuristiques pour résoudre ce problème
complexe de placement de services de sécurité dans l’IoT. Enfin, une comparaison avec
les approches existantes dans la littérature sera réalisée pour évaluer l’efficacité et la
performance de notre approche.Côte titre : MAI/0736 En ligne : https://drive.google.com/file/d/18Ew94yLj97PJyhxDu0kbmi6-U2pQgStu/view?usp=drive [...] Format de la ressource électronique : Placement de services de sécurité dans l’IoT [texte imprimé] / Younes Abid, Auteur ; Layachi-Houssem Bendana, Auteur ; Samir Balbal, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2023 . - 1 vol (67 f .) ; 29cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Internet des Objets
Ensemble dominant minimalIndex. décimale : 004 Informatique Résumé : L’émergence de l’Internet des objets (IoT) a suscité un intérêt croissant dans notre
société, en permettant la connectivité d’un large éventail d’objets, des plus petits aux plus
grands. Cependant, la sécurité représente un défi majeur dans le domaine de l’IoT, étant
donné le nombre massif d’appareils connectés et les données sensibles qui circulent sur
les réseaux. Assurer la protection de ces informations contre les cyberattaques revêt une
importance capitale. Dans ce contexte, le placement optimal des services de sécurité dans
l’IoT joue un rôle crucial pour garantir la sécurité des appareils et des données. Une approche
prometteuse pour optimiser ce placement est l’utilisation de l’ensemble dominant
minimal (MDS) dans les graphes, permettant d’optimiser l’allocation des ressources de
sécurité. Cependant, le problème de l’ensemble dominant minimal est considéré comme
NP-difficile, rendant sa résolution complexe. Ainsi, l’objectif de cette étude est d’explorer
l’utilisation de méthodes heuristiques et métaheuristiques pour résoudre ce problème
complexe de placement de services de sécurité dans l’IoT. Enfin, une comparaison avec
les approches existantes dans la littérature sera réalisée pour évaluer l’efficacité et la
performance de notre approche.Côte titre : MAI/0736 En ligne : https://drive.google.com/file/d/18Ew94yLj97PJyhxDu0kbmi6-U2pQgStu/view?usp=drive [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0736 MAI/0736 Mémoire Bibliothéque des sciences Français Disponible
Disponible
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 algorithmIndex. 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 .................................................................................................................. 60Cô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 algorithmIndex. 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 .................................................................................................................. 60Cô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
