Skip to Main content Skip to Navigation
Conference papers

De la difficulté de trouver des chemins dissimilaires

Ali Al Zoobi 1 David Coudert 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Lorsque l'on demande à son GPS un chemin pour aller à La Rochelle, celui-ci propose généralement plusieurs chemins assez différents les uns des autres : l'un par l'autoroute, l'autre par la côte, un pas cher, etc. La notion de (dis)similarité entre deux chemins a été définie, dans la littérature, de différentes manières qui toutes sont liées à un ratio entre la longueur de leur intersection et une certaine fonction de leurs longueurs. Nous étudions la complexité de plusieurs variantes du problème du calcul de chemins "dissimilaires" (dont la mesure de similarité n'excède pas un certain seuil) entre deux sommets d'un graphe orienté et pondéré. Pour quatre des mesures les plus étudiées dans la littérature, nous donnons une preuve unifiée et simple du fait que trouver $k$ plus courts chemins dissimilaires est NP-complet. En pratique, ce que l'on cherche est une alternative à un ou des chemins que l'on connait a priori. Nos résultats principaux concernent ce type de problème. Plus précisément, pour chacune des quatre mesures considérées, nous montrons que si $k\geq 2 $chemins sont donnés, en trouver un nouveau qui soit dissimilaire des premiers est NP-complet. Enfin, nous montrons que si un chemin $P$ est donné, trouver un plus court chemin parmi ceux qui sont dissimilaires de $P$ est NP-complet. Ce dernier résultat est à mettre en contraste avec le fait que, pour l'une des mesures, trouver un chemin dissimilaire à un chemin donné peut être résolu très simplement en temps polynomial.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03219987
Contributor : Ali Al Zoobi Connect in order to contact the contributor
Submitted on : Monday, September 20, 2021 - 4:39:31 PM
Last modification on : Wednesday, September 22, 2021 - 3:40:02 AM

File

On_the_k_top_shortest_paths_wi...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03219987, version 2

Citation

Ali Al Zoobi, David Coudert, Nicolas Nisse. De la difficulté de trouver des chemins dissimilaires. ALGOTEL 2021 - 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2021, La Rochelle, France. ⟨hal-03219987v2⟩

Share

Metrics

Record views

31

Files downloads

21