現代の最短経路アルゴリズムとグラフ最適化技術の概要

リンク一覧

概要と1. はじめに

1.1 私たちの貢献

1.2 設定

1.3 アルゴリズム

1. 関連研究

2. アルゴリズム

   3.1 構造分解フェーズ

   3.2 ルーティングフェーズ

   3.3 WormHoleのバリエーション

3. 理論的分析

   4.1 前提条件

   4.2 内部リングの準線形性

   4.3 近似誤差

   4.4 クエリ複雑性

4. 実験結果

   5.1 WormHole𝐸、WormHole𝐻とBiBFS

   5.2 インデックスベースの手法との比較

   5.3 基本要素としてのWormHole：WormHole𝑀

参考文献

2 関連研究

最短経路と距離に関する研究は膨大にあり、数十年にわたって、様々な設定のために設計された何百ものアルゴリズムとヒューリスティックが含まれています。ここでは、私たちの研究に最も密接に関連するいくつかの研究のみをレビューします。より包括的な概要については、調査論文[42, 55]およびそこに含まれる参考文献を参照してください。

\ インデックスベースのアプローチ。前述のように、ランドマーク/スケッチアプローチ[37, 61, 62]に基づくアルゴリズムが広く普及しており、Pruned Landmark Labeling (PLL)[5]がおそらく最も影響力のあるものです。これらのアルゴリズムは2段階の手順に従います：最初のステップでは重要度に応じて頂点の順序付けを生成し（異なるヒューリスティックに基づく）、2番目のステップではその順序に従って構築された剪定された最短経路木からラベル付けを生成します。その後、任意の頂点ペア𝑠とtの間の最短距離は、それらのラベルに基づいて迅速に回答できます。しかし、剪定があっても、PLLは重要なセットアップ時間を必要とします。そのため、それを並列化する多くの試みがありました[29, 37, 39]。

\ 埋め込みベースのアプローチ。最近のアプローチの中には、グラフの埋め込みを活用して最短経路を推定するものがあります。表現学習のように、ノードのペア間の距離の効率的な表現を見つけることを目指しています[64, 65]。現代的な研究の流れでは、最短経路の問い合わせに答えるために、ツリー分解と密接に関連するグラフの双曲線埋め込みも考慮されています[11, 33]。最近の研究では、GPUベースの深層学習手法を使用してこのプロセスを加速することも検討されています[35, 47, 48]。Query-by-Sketch[57]は、関連しているが比較できない、最短経路グラフ問い合わせに答えるタスクを考慮しており、目標は与えられた頂点ペア間のすべての最短経路を正確に含むサブグラフを計算することです。彼らはスケーラビリティと問い合わせ時間を改善するための代替ラベル付けスキームを提案しています。

\

\ コア-周辺部ベースのアプローチ。他のいくつかの研究はネットワークのコア-周辺部構造を活用しています[6, 13, 38]。BradyとCohen[13]はコンパクトなルーティングスキームを使用して、周辺部が森に似ていることに基づいた小さな加算誤差を持つアルゴリズムを設計しています。Akiba、SommerおよびKawarabayashi[6]はコア外の低いツリー幅の特性を活用し、[38]では、著者らは大規模グラフの前処理時間を改善するためにコアツリーベースのインデックスを設計しています。これらの結果すべてにおいて、メモリオーバーヘッドは超線形であることに注意します。

\ 最悪ケースのグラフ。理論的な側面では、最悪ケースのグラフにおける正確および近似最短経路に関する多くの結果があります（例：[19, 20, 22, 49, 51, 67]）、昨年のような最近の改善もあります。これらのほとんどは、Aingworthら[4]の先駆的な研究で最初に調査された2近似ケースに焦点を当てています。正確および近似最短経路アルゴリズムに関するZwickの調査[66]、および前処理コストを下げることに重点を置いた一般グラフの距離オラクルに関するSenの調査[53]を読者に紹介します。特筆すべきは、大規模ネットワークで一般的な最悪ケースを超える構造的仮定、すなわちコア-周辺部構造を前提としているため、私たちの結果とアルゴリズムは最悪ケースの理論的文献とは大きく異なります。

\

:::info 著者：

(1) Talya Eden、バル・イラン大学（talyaa01@gmail.com）；

(2) Omri Ben-Eliezer、MIT（omrib@mit.edu）；

(3) C. Seshadhri、UCサンタクルーズ（sesh@ucsc.edu）。

:::

:::info この論文はarxivで入手可能であり、CC BY 4.0ライセンスの下で提供されています。

:::

\