Propriétés métriques des grands graphes / Guillaume Ducoffe ; sous la direction de David Coudert

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Catalogue Worldcat

Graphes, Théorie des

Algorithmes

Hyperboles (mathématiques)

Nash, Variétés de

Fonctions booléennes

Coudert, David (1973-....) (Directeur de thèse / thesis advisor)

Chepoi, Victor (Rapporteur de la thèse / thesis reporter)

Viennot, Laurent (Rapporteur de la thèse / thesis reporter)

Flammini, Michele (19..-....) (Membre du jury / opponent)

Gavoille, Cyril (1970-....) (Membre du jury / opponent)

Nisse, Nicolas (1980-....) (Membre du jury / opponent)

Tarjan, Robert Endre (1948-....) (Membre du jury / opponent)

Université Côte d'Azur (2015-2019) (Organisme de soutenance / degree-grantor)

École doctorale Sciences et technologies de l'information et de la communication (Sophia Antipolis, Alpes-Maritimes) (Ecole doctorale associée à la thèse / doctoral school)

Université de Nice (1965-2019) (Autre partenaire associé à la thèse / thesis associated third party)

Institut national de recherche en informatique et en automatique (France). Unité de recherche (Sophia Antipolis, Alpes-Maritimes) (Laboratoire associé à la thèse / thesis associated laboratory)

Laboratoire Informatique, signaux et systèmes (Sophia Antipolis, Alpes-Maritimes) (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : Les grands réseaux de communication sont partout, des centres de données avec des millions de serveurs jusqu’aux réseaux sociaux avec plusieurs milliards d’utilisateurs.Cette thèse est dédiée à l’étude fine de la complexité de différents problèmes combinatoires sur ces réseaux. Dans la première partie, nous nous intéressons aux propriétés des plongements des réseaux de communication dans les arbres. Ces propriétés aident à mieux comprendre divers aspects du trafic dans les réseaux (tels que la congestion). Plus précisément, nous étudions la complexité du calcul de l’hyperbolicité au sens de Gromov et de paramètres des décompositions arborescentes dans les graphes. Ces paramètres incluent la longueur arborescente (treelength) et l’épaisseur arborescente (treebreadth). Au passage, nous démontrons de nouvelles bornes sur ces paramètres dans de nombreuses classes de graphes, certaines d’entre elles ayant été utilisées dans la conception de réseaux d’interconnexion des centres de données. Le résultat principal dans cette partie est une relation entre longueur et largeur arborescentes (treewidth), qui est un autre paramètre très étudié des graphes. De ce résultat, nous obtenons une vision unifiée de la ressemblance des graphes avec un arbre, ainsi que différentes applications algorithmiques. Nous utilisons dans cette partie divers outils de la théorie des graphes et des techniques récentes de la théorie de la complexité

Résumé / Abstract : Large scale communication networks are everywhere, ranging from data centers withmillions of servers to social networks with billions of users. This thesis is devoted tothe fine-grained complexity analysis of combinatorial problems on these networks.In the first part, we focus on the embeddability of communication networks totree topologies. This property has been shown to be crucial in the understandingof some aspects of network traffic (such as congestion). More precisely, we studythe computational complexity of Gromov hyperbolicity and of tree decompositionparameters in graphs – including treelength and treebreadth. On the way, we givenew bounds on these parameters in several graph classes of interest, some of thembeing used in the design of data center interconnection networks. The main resultin this part is a relationship between treelength and treewidth: another well-studiedgraph parameter, that gives a unifying view of treelikeness in graphs and has algorithmicapplications. This part borrows from graph theory and recent techniques incomplexity theory. The second part of the thesis is on the modeling of two privacy concerns with social networking services. We aim at analysing information flows in these networks,represented as dynamical processes on graphs. First, a coloring game on graphs isstudied as a solution concept for the dynamic of online communities. We give afine-grained complexity analysis for computing Nash and strong Nash equilibria inthis game, thereby answering open questions from the literature. On the way, wepropose new directions in algorithmic game theory and parallel complexity, usingcoloring games as a case example