著者

小池 敦 定兼 邦彦

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2016-AL-159, no.7, pp.1-8, 2016-09-16

---

本論文では,道路ネットワーク上の経路探索クエリについて,新しいアルゴリズムを提案する.提案手法は Hub Labeling や Pruned Highway Labeling と同様,ラベリング法に基づくものである.前処理において,入力グラフを複数の木に分解し,各ノードが hub ノード集合の代わりに木の ID の集合を保持することでラベルサイズを削減させる.本論文ではアルゴリズムを実装し,米国の道路ネットワークを用いて評価を行うことで,提案アルゴリズムの有効性を示す.