Algorithmes exacts et exponentiels pour des problèmes de graphes
De nombreux problèmes algorithmiques sont difficiles , dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l entrée, soit parce qu ils sont NP-difficiles, soit, pour certains problèmes d énumération, à cause du nombre exponentiel d'objets à énumérer. Depui...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | , , , , , |
| Médium: | Thèse numérique |
| Jazyk: | Français |
| Vydáno: |
2015.
|
| Témata: | |
| On-line přístup: | Accès au texte intégral https://theses.univ-orleans.fr/public/2015ORLE2022_va.pdf http://www.theses.fr/2015ORLE2022/abes https://theses.hal.science/tel-01309228 |
| Poznámka: |
Titre provenant de l'écran-titre Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) Autre(s) contribution(s) : Vincent T'kindt (Président du jury) ; Ioan Todinca, Mathieu Liedloff, Vincent T'kindt, Frédéric Havet, Cristina Bazgan, Alexandre Pinlou (Membre(s) du jury) ; Frédéric Havet, Cristina Bazgan (Rapporteur(s)) |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Exact exponential algorithms for solving graph problems summary |
| Shrnutí: | De nombreux problèmes algorithmiques sont difficiles , dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l entrée, soit parce qu ils sont NP-difficiles, soit, pour certains problèmes d énumération, à cause du nombre exponentiel d'objets à énumérer. Depuis une quinzaine d années on trouve un intérêt grandissant dans la littérature pour la conception d'algorithmes exacts sophistiqués afin de les résoudre le plus efficacement possible. Dans le cadre de cette thèse, nous nous intéressons à la conception d'algorithmes exacts exponentiels autour de trois problèmes difficiles. Nous étudions tout d'abord le problème d'optimisation Ensemble Connexe Tropical pour lequel nous décrivons un algorithme afin de le résoudre en général, puis un algorithme de branchement plus rapide pour le résoudre sur les arbres, ce problème restant difficile même dans ce cas. Nous nous intéressons ensuite au problème d'énumération Ensembles Dominants Minimaux, pour lequel nous donnons des algorithmes résolvant ce problème dans les graphes splits, cobipartis, ainsi que dans les graphes d'intervalles. Nous déduisons des bornes supérieures sur le nombre d'ensembles dominants minimaux admis par de tels graphes. La dernière étude de cette thèse concerne le problème d'optimisation Domination Romaine Faible dans lequel, étant donné un graphe nous cherchons à construire une fonction de pondération selon certaines propriétés. Le problème est NP-difficile en général, mais nous donnons un algorithme glouton linéaire calculant une telle fonction pour les graphes d'intervalles. Many algorithmic problems are hard , in the sense of we do not know how to solve them in polynomialtime, either because they are NP-hard, or, for some enumeration problems, because the number of objectsto be produced is exponential. During the last fifteen years there was a growing interest in the design of exact algorithms to solve such problems as efficiently as possible. In the context of this thesis, we focus on the design of exponential exact algorithms for three hard problems. First, we study the optimisation problem Tropical Connected Set for which we describe an algorithm to solve it in the general case, then a faster branch-and-reduce algorithm to solve it on trees; the problem remains difficult even in this case. Secondly we focus on the Minimal Dominating Sets enumeration problem, for which we give algorithms to solve it on split, cobipartite and intervals graphs. As a byproduct, we establish upper bounds on the number of minimal dominating sets in such graphs. The last focus of this thesis concerns the Weak Roman Domination optimisation problem for which, given a graph, the goal is to build a weight function under some properties. The problem is NP-hard in general, but we give a linear greedy algorithm which computes such a function on interval graphs. |
|---|---|
| Popis jednotky: | Titre provenant de l'écran-titre Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) Autre(s) contribution(s) : Vincent T'kindt (Président du jury) ; Ioan Todinca, Mathieu Liedloff, Vincent T'kindt, Frédéric Havet, Cristina Bazgan, Alexandre Pinlou (Membre(s) du jury) ; Frédéric Havet, Cristina Bazgan (Rapporteur(s)) |
| Médium: | Configuration requise : un logiciel capable de lire un fichier au format : PDF |