Mardi 20 Novembre 2007, 14h, Salle S16 (Passage Saumon niveau -1)
-
Orateur/Speaker :
Éric Colin de Verdière, ENS Paris, CNRS
-
Titre/Title :
Plus courts chemins disjoints dans un graphe planaire
-
Résumé/Abstract :
Étant donné un graphe G et des paires de sommets de G, le problème de
déterminer s'il existe des chemins sommets-disjoints reliant ces paires
est connu pour être NP-dur, même dans un graphe planaire. En revanche,
il admet un algorithme linéaire si G est planaire et qu'il existe deux
faces s et t telles que chaque paire de sommets contient un sommet
incident à s et l'autre à t.
Nous nous plaçons dans ce cas, supposant en outre les arêtes de G munies
d'une longueur positive. Nous montrons comment calculer des chemins
sommets-disjoints reliant les paires de sommets requises, de sorte que
la longueur totale des chemins soit minimale. L'algorithme a une
complexité O(kn log n) où k est le nombre de paires de sommets et n est
la complexité de G. La méthode repose sur des algorithmes de flot et de
potentiel dans des graphes appropriés.
Travail en commun avec Alexander Schrijver, CWI, Amsterdam.
Voir preprint.