Une Brève Revue des Algorithmes Modernes de Plus Court Chemin et des Techniques d'Optimisation de Graphes

Table des liens

Abstrait et 1. Introduction

1.1 Notre contribution

1.2 Cadre

1.3 L'algorithme

1. Travaux connexes

2. Algorithme

   3.1 La phase de décomposition structurelle

   3.2 La phase de routage

   3.3 Variantes de WormHole

3. Analyse théorique

   4.1 Préliminaires

   4.2 Sous-linéarité de l'anneau intérieur

   4.3 Erreur d'approximation

   4.4 Complexité des requêtes

4. Résultats expérimentaux

   5.1 WormHole𝐸, WormHole𝐻 et BiBFS

   5.2 Comparaison avec les méthodes basées sur l'indexation

   5.3 WormHole comme primitive : WormHole𝑀

Références

2 TRAVAUX CONNEXES

Il existe un vaste corpus de recherches sur les plus courts chemins et les distances, s'étendant sur plusieurs décennies et comprenant des centaines d'algorithmes et d'heuristiques conçus pour une variété de contextes. Ici, nous ne passons en revue que plusieurs travaux qui sont les plus étroitement liés aux nôtres. Pour une vue d'ensemble plus complète, voir les études [42, 55] et les références qui y figurent.

\ Approches basées sur l'indexation. Comme mentionné précédemment, un ensemble omniprésent d'algorithmes est basé sur des approches de points de repère/esquisse [37, 61, 62], avec Pruned Landmark Labeling (PLL) [5] étant peut-être le plus influent. Ces algorithmes suivent une procédure en deux étapes : la première étape génère un ordonnancement des sommets selon leur importance (basé sur différentes heuristiques), et la deuxième étape génère un étiquetage à partir d'arbres de plus courts chemins élagués construits selon l'ordonnancement. Ensuite, la distance la plus courte entre une paire arbitraire de sommets 𝑠 et t peut être répondue rapidement en fonction de leurs étiquettes. Cependant, même avec l'élagage, PLL nécessite un temps de configuration important. Par conséquent, il y a eu de nombreuses tentatives pour le paralléliser [29, 37, 39].

\ Approches basées sur l'intégration. Certaines approches récentes exploitent les intégrations de graphes pour estimer les plus courts chemins. Comme dans l'apprentissage de représentation, elles cherchent à trouver des représentations efficaces des distances entre paires de nœuds [64, 65]. Une ligne de travail moderne considère également les intégrations hyperboliques des graphes, qui sont étroitement liées aux décompositions d'arbres, pour répondre aux requêtes de plus court chemin [11, 33]. Des travaux récents ont également examiné l'accélération de ce processus en utilisant des méthodes d'apprentissage profond basées sur GPU [35, 47, 48]. Query-by-Sketch [57] considère la tâche, liée mais incomparable, de répondre aux requêtes de graphe de plus court chemin, où l'objectif est de calculer un sous-graphe contenant exactement tous les plus courts chemins entre une paire donnée de sommets. Ils proposent un schéma d'étiquetage alternatif pour améliorer l'évolutivité et les temps de requête.

\

\ Approches basées sur le noyau-périphérie. Plusieurs autres travaux exploitent la structure noyau-périphérie des réseaux [6, 13, 38]. Brady et Cohen [13] utilisent des schémas de routage compacts pour concevoir un algorithme avec une petite erreur additive basée sur la ressemblance de la périphérie à une forêt. Akiba, Sommer et Kawarabayashi [6] exploitent la propriété de faible largeur d'arbre en dehors du noyau, et dans [38], les auteurs conçoivent un index basé sur Core-Tree afin d'améliorer les temps de prétraitement sur des graphes massifs. Nous notons que dans tous ces résultats, la surcharge de mémoire est super-linéaire.

\ Graphes de pire cas. Sur le plan théorique, il y a eu de nombreux résultats sur les plus courts chemins exacts et approximatifs dans les graphes de pire cas, par exemple, [19, 20, 22, 49, 51, 67], avec des améliorations aussi récentes que l'année dernière. La plupart d'entre eux se concentrent sur le cas d'approximation 2, d'abord étudié dans le travail fondateur d'Aingworth et al. [4]. Nous dirigeons les lecteurs vers l'étude de Zwick [66] sur les algorithmes de plus court chemin exacts et approximatifs, et l'étude de Sen [53] sur les oracles de distance pour les graphes généraux avec un accent sur la réduction du coût de prétraitement. Notamment, parce que nous faisons une hypothèse structurelle au-delà du pire cas qui est commune dans les grands réseaux, à savoir, une structure noyau-périphérie, nos résultats et notre algorithme diffèrent substantiellement de la littérature théorique du pire cas.

\

:::info Auteurs :

(1) Talya Eden, Université Bar-Ilan (talyaa01@gmail.com) ;

(2) Omri Ben-Eliezer, MIT (omrib@mit.edu) ;

(3) C. Seshadhri, UC Santa Cruz (sesh@ucsc.edu).

:::

:::info Cet article est disponible sur arxiv sous licence CC BY 4.0.

:::

\