Algorithmes de graphes séquentiels et distribués : algorithmes paramétrés via des cliques maximales potentielles : modèle de diffusion dans une clique congestionnée
Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects...
Wedi'i Gadw mewn:
| Prif Awdur: | |
|---|---|
| Awduron Eraill: | , , , , , |
| Fformat: | Thèse numérique |
| Iaith: | Anglais |
| Cyhoeddwyd: |
2017.
|
| Pynciau: | |
| Mynediad Ar-lein: | Accès au texte intégral https://theses.univ-orleans.fr/public/2017ORLE2001_va.pdf http://www.theses.fr/2017ORLE2001/abes |
| Nodyn: |
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) : Cyril Gavoille (Président du jury) ; Ioan Todinca, Cyril Gavoille, Pierre Fraigniaud, Christophe Paul, Nicolas Nisse, Florent Becker (Membre(s) du jury) ; Pierre Fraigniaud, Christophe Paul (Rapporteur(s)) |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Sequential and distributed graph algorithms |
| LEADER | 05448nam a22004337a 4500 | ||
|---|---|---|---|
| 001 | 641244 | ||
| 008 | 171024s2017 xxe ||| |||| 00| 0 eng d | ||
| 009 | PPN219485658 | ||
| 041 | 0 | |a eng |b fre |b eng | |
| 082 | |a 518.5 | ||
| 084 | |a 510 | ||
| 100 | 1 | |a Montealegre Barba, Pedro, |d 1987- | |
| 240 | 1 | 0 | |a Sequential and distributed graph algorithms |
| 245 | 1 | 0 | |a Algorithmes de graphes séquentiels et distribués : |b algorithmes paramétrés via des cliques maximales potentielles : modèle de diffusion dans une clique congestionnée |c Pedro Montealegre Barba ; sous la direction de Ioan Todinca. |
| 256 | |a Données textuelles | ||
| 260 | |c 2017. | ||
| 500 | |a Titre provenant de l'écran-titre | ||
| 500 | |a Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) | ||
| 500 | |a Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) | ||
| 500 | |a Autre(s) contribution(s) : Cyril Gavoille (Président du jury) ; Ioan Todinca, Cyril Gavoille, Pierre Fraigniaud, Christophe Paul, Nicolas Nisse, Florent Becker (Membre(s) du jury) ; Pierre Fraigniaud, Christophe Paul (Rapporteur(s)) | ||
| 502 | |a Thèse de doctorat. Informatique. Orléans. 2017 | ||
| 520 | |a Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects algorithmiques de deux structures de graphes appelés séparateurs minimaux et cliques maximales potentielles. Ces deux objets sont au coeur d'un méta-théorème dû à Fomin, Todinca and Villanger (SIAM J. Comput. 2015), qui affirme qu'une grande famille des problèmes d'optimisation peut être résolue en temps polynomial, si le graphe d'entrée contient un nombre polynomial de séparateurs minimaux. La contribution de cette partie consiste à prolonger le méta-théorème de Fomin et al. de deux manières : d'un côté, on l'adapte pour qu'il soit valide pour une plus grande famille des problèmes ; de l'autre, on étend ces résultats à des version paramétrées, pour certains paramètres des graphes. La deuxième partie de la thèse correspond à une étude du modèle appelé Diffusion dans une Clique Congestionnée . Dans ce modèle, les sommets d'un graphe communiquent entre eux dans des rondes synchrones, en diffusant un message de petite taille, visible par tout autre sommet. L'objectif ici est d'élaborer des protocoles qui reconnaissent des classes de graphes, en minimisant la taille des messages et le nombre de rondes. La contribution de cette partie est l'étude du rôle du hasard dans ce modèle, et la conception de protocoles pour la reconnaissance et la reconstruction des certaines classes des graphes. | ||
| 520 | |a This thesis is about structural and algorithmic aspects of graphs. It is divided in two parts, which are about two different studies: one part is about centralized-sequential algorithms, and the other part is about distributed algorithms. In the first part of the thesis we study algorithmic applications of two graph structures called minimal separators and potential maximal cliques. These two objects are in the core of a meta-theorem due to Fomin, Todinca and Villanger (SIAM J. Comput. 2015), which states that a large family of graph optimization problems can be solved in polynomial time, when the input is restricted to the family of graphs with polynomially many minimal separators. The contribution of this part of the thesis is to extend the meta-theorem of Fomin et al. in two ways. On one hand, we adapt it to be valid into a larger family of problems. On the other hand, we extend it into a parameterized version, for several graph parameters. In the second part of this thesis we study the broadcast congested clique model. In this model, the nodes of a graph communicate in synchronous rounds, broadcasting a message of small size visible to every other node. The goal is to design protocols that recognize graph classes minimizing the number of rounds and the message sizes. The contribution of this part is to explore the role of randomness on this model, and provide protocols for the recognition and reconstruction of some graph classes. | ||
| 538 | |a Configuration requise : un logiciel capable de lire un fichier au format : PDF | ||
| 650 | |a Théorie des graphes | ||
| 650 | |a Algorithmes | ||
| 650 | |a Algorithmes parallèles | ||
| 650 | |a Thèses et écrits académiques | ||
| 700 | 1 | |a Todinca, Ioan, |d 19..- |4 ths |4 opn | |
| 700 | 1 | |a Gavoille, Cyril, |d 1970- |4 opn | |
| 700 | 1 | |a Fraigniaud, Pierre, |d 19..-...., |c informaticien. |4 opn | |
| 700 | 1 | |a Paul, Christophe, |d 19..-...., |c directeur de recherche en informatique. |4 opn | |
| 700 | 1 | |a Nisse, Nicolas, |d 1980- |4 opn | |
| 700 | 1 | |a Becker, Florent, |d 1987- |4 opn | |
| 710 | 2 | |a Université d'Orléans. |4 dgg | |
| 856 | 4 | |q PDF |s 1877781 |u http://www.theses.fr/2017ORLE2001/document |z Accès au texte intégral | |
| 856 | 4 | |u https://theses.univ-orleans.fr/public/2017ORLE2001_va.pdf | |
| 856 | 4 | |u http://www.theses.fr/2017ORLE2001/abes | |
| 997 | |0 641244 |1 Thèse numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||