Décomposition de graphes en plus courts chemins et en cycles de faible excentricité
no title available
par Léo PLANCHE sous la direction de Étienne BIRMELÉ
Thèse de doctorat en Mathématiques informatique
ED 386 Sciences Mathématiques de Paris Centre

Soutenue le Friday 23 November 2018 à Sorbonne Paris Cité

Sujets
  • Graphes, Théorie des
  • Laminaires

Depuis le 1er janvier 2012, les thèses de doctorat soutenues ou préparées à l’Université Paris Descartes sont déposées au format électronique, sous licence Creative Commons.

Consultation de la thèse sur d’autres sites :

Theses.fr (Version intégrale de la thèse (pdf))
TEL (Version intégrale de la thèse (pdf))

Description en anglais
Description en français
Mots clés
Théorie des graphes, Cycle isométrique, Excentricité, Plus court chemin, Domination, Graphe de reads, Label de distances, Laminaire
Resumé
En collaboration avec des chercheurs en biologie à Jussieu, nous étudions des graphes issus de données biologiques afin de d'en améliorer la compréhension. Ces graphes sont constitués à partir de fragments d'ADN, nommés reads. Chaque read correspond à un sommet, et deux sommets sont reliés si les deux séquences d'ADN correspondantes ont un taux de similarité suffisant. Ainsi se forme des graphes ayant une structure bien particulière que nous nommons hub-laminaire. Un graphe est dit hub-laminaire s'il peut être résumé en quelques plus courts chemins dont tous les sommets du graphe soient proche. Nous étudions en détail le cas où le graphe est composé d'un unique plus court chemin d'excentricité faible, ce problème a été initialement défini par Dragan 2017. Nous améliorons la preuve d'un algorithme d'approximation déjà existant et en proposons un nouveau, effectuant une 3-approximation en temps linéaire. De plus, nous analysons le lien avec le problème de k-laminarité défini par Habib 2016, ce dernier consistant en la recherche d'un diamètre de faible excentricité. Nous étudions ensuite le problème du cycle isométrique de plus faible excentricité. Nous montrons que ce problème est NP-complet et proposons deux algorithmes d'approximations. Nous définissons ensuite précisément la structure "hub-laminaire" et présentons un algorithme d'approximation en temps O(nm). Nous confrontons cet algorithme à des graphes générés par une procédure aléatoire et l'appliquons à nos données biologiques. Pour finir nous montrons que le calcul du cycle isométrique d'excentricité minimale permet le plongement d'un graphe dans un cercle avec une distorsion multiplicative faible. Le calcul d'une décomposition hub-laminaire permet quant à lui une représentation compacte des distances avec une distorsion additive bornée.