Doctorat
Equipe : Graphes, Algorithmes et Combinatoire
Algorithmes pour voyager sur un graphe contenant des blocages
Début le 01/01/1970
Direction : TOMASIK, Joanna
Ecole doctorale : ED STIC 580
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : l'amphi IV du bâtiment Eiffel de CentraleSupélec
Soutenue le 03/12/2019 devant le jury composé de :
Rapporteurs :
M. Bruno Escoffier (Sorbonne Université)
M. Ignasi Sau (Université de Montpellier)
M. Stephan Westphal (TU Clausthal)
Examinateurs :
Mme. Cristina Bazgan (Université Paris-Dauphine)
M. Olivier Bournez (École polytechnique)
M. Yannis Manoussakis (Université Paris-Sud)
Directeur de thèse :
Mme. Joanna Tomasik (CentraleSupélec, Université Paris-Sud)
Encadrant :
M. Arpad Rimmel (CentraleSupélec, Université Paris-Sud)
Activités de recherche :
Résumé :
Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.
Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s_1,...,s_k} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre seconde contribution est la construction d'un algorithme qui compte les coupes minimums entre deux ensembles S et T en temps 2^{O(p log p)}n^{O(1)}.
Nous présentons ensuite plusieurs résultats sur le ratio de compétitivité des stratégies déterministes et randomisées pour le problème du voyageur canadien.
Nous prouvons que les stratégies randomisées n'utilisant pas de mémoire ne peuvent pas améliorer le ratio 2k+1. Nous apportons également des éléments concernant les bornes inférieures de compétitivité de l'ensemble des stratégies randomisées. Puis, nous étudions la compétitivité en distance d'un groupe de voyageurs avec et sans communication. Enfin, nous nous penchons sur la competitivité des stratégies déterministes pour certaines familles de graphes. Deux stratégies, avec un ratio inférieur à 2k+1 sont proposées: une pour les graphes cordaux avec poids uniformes et l'autre pour les graphes où la taille de la plus grande coupe minimale séparant s et t est au plus k.
