Algorithmic aspects of reachability in temporal graphs

Aspects algorithmiques de l'atteignabilité dans les graphes Les graphes temporels sont une extension des graphes et représentent des réseaux évoluant au fil du temps. Dans ce contexte, les arêtes peuvent être disponibles ou non à certains moments, et sont appelées arêtes temporelles. La longueur, ou une autre propriété associée à une arête, qui est classiquement capturée par le poids d'un arc, peut maintenant avoir différentes valeurs en fonction du moment où l'arête est disponible. Les notions classiques de la théorie des graphes nécessitent maintenant de nouvelles définitions tenant compte de la dimension temporelle. Une marche temporelle, par exemple, correspond à une séquence d'arêtes temporelles qui sont adjacentes l'une avec la suivante et qui sont disponibles l'une après la suivante. Un noed est temporellement accessible à partir d'un autre s'il existe une marche temporelle allant de l'un à l'autre. Dans cette thèse, nous explorons des problèmes qui peuvent être regroupés en deux thèmes principaux : le calcul de la marche temporelle et la temporisation d'un graphe statique. Nous étudions le problème du calcul des marches temporelles à coût minimal, le terme "coût" a ici un sens très large. En effet, nous introduisons une structure de coût algébrique qui peut être instanciée afin de modéliser tous les critères classiques d'optimisation de marche dans les graphes temporels, tels que le temps d'arrivée ou la durée, ainsi que leur combinaison linéaire, ou leur composition lexicographique. De plus, nous étudions ce problème dans des graphes temporels soumis à des contraintes sur le temps d'attente. Notre principal résultat sur ce sujet est un algorithme scannant les arêtes temporelles pour calculer les marches de coût minimal depuis une source donnée. Il prend en entrée la représentation classique de graphe étendu dans le temps sous l'hypothèse de son acyclicité, et s'exécute en temps linéaire. Nous montrons également que le cadre dans lequel nous obtenons un temps linéaire est le plus large possible : un facteur logarithmique supplémentaire est nécessaire lorsque l'hypothèse d'acyclicité est abandonnée ou lorsqu'une représentation plus faible du graphe temporel est utilisée. Lorsque nous parlons de temporisation, nous nous référons au problème de conception de réseau qui consiste à transformer un graphe statique en un graphe temporel tout en optimisant un certain critère. En particulier, nous étudions un problème inspiré par l'optimisation des horaires de bus, métro ou tramway, dans un réseau de transport public où chaque trajectoire d'un véhicule est modélisée par une marche dans le graphe orienté représentant la carte du réseau. Nous considérons le problème de la transformation d'une collection de telles marches (appelées trajets) dans un graphe orienté en un graphe temporel en assignant une heure de départ à chaque trajet de manière à maximiser l'atteignabilité entre les paires de noeds. Nous obtenons plusieurs résultats de complexité. Nous montrons notamment que la maximisation de l'atteignabilité via la temporisation des trajets est difficile à approximer avec un facteur meilleur que sqrt(n)/12 dans un digraphe à n sommets, et ceci, même si nous supposons que pour chaque paire de noeds, il existe une temporisation des trajets qui les relie. En revanche, en ajoutant une notion de symétrie sur les trajets, c'est-à-dire, que pour chaque trajet il existe un trajet symétrique visitant les mêmes noeds dans l'ordre inverse, nous montrons qu'il doit exister une temporisation des trajets reliant une fraction constante de toutes les paires. Notons que la symétrie est une hypothèse raisonnable dans le contexte des réseaux de transport public, où une ligne de bus ou de métro comporte généralement des trajets dans les deux sens.