| アイテムタイプ |
レポート / Report(1) |
| 公開日 |
2019-03-12 |
| タイトル |
|
|
タイトル |
NII Technical Report (NII-2008-007E)：Approximate Shortest Path Queries in Graphs Using Voronoi Duals |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| キーワード |
|
|
言語 |
ja |
|
主題Scheme |
Other |
|
主題 |
テクニカルレポート |
| キーワード |
|
|
言語 |
en |
|
主題Scheme |
Other |
|
主題 |
Technical Report |
| 資源タイプ |
|
|
資源 |
http://purl.org/coar/resource_type/c_6501 |
|
タイプ |
departmental bulletin paper |
| ID登録 |
|
|
ID登録 |
10.20736/0000001245 |
|
ID登録タイプ |
JaLC |
| 著者 |
Sommer, Christian
Houle, Michael E.
Wolff, Martin
本位田, 真一
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
We propose an approximation method to answer shortest path queries in graphs, based on hierarchical random sampling and Voronoi duals. The lowest level of the hierarchy stores the initial graph. At each higher level, we compute a simplification of the graph on the level below, by selecting a constant fraction of nodes. Edges are generated as the Voronoi dual within the lower level, using the selected nodes as Voronoi sites. This hierarchy allows for fast computation of approximate shortest paths for general graphs. The time-quality tradeoff decision can be made at query time. We provide bounds on the approximation ratio of the path lengths. |
|
言語 |
en |
| 書誌情報 |
ja : NIIテクニカル・レポート
en : NII Technical Report
p. none,
発行日 2008-08-18
|
| 出版者 |
|
|
出版者 |
国立情報学研究所 |
|
言語 |
ja |
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
1346-5597 |
NII Technical Report (NII-2008-007E)：Approximate Shortest Path Queries in Graphs Using Voronoi Duals (306.0 kB)
