| 大会名称 |
| 2021年 ソサイエティ大会 |
| 大会コ－ド |
| 2021S |
| 開催年 |
|
2021
|
| 発行日 |
|
2021/8/31
|
| セッション番号 |
|
BS-6
|
| セッション名 |
|
Network and Service Design, Control and Management
|
| 講演日 |
|
2021/9/16
|
| 講演場所(会議室等) |
|
Meeting 22
|
| 講演番号 |
|
BS-6-9
|
| タイトル |
|
A Study on a Solution for Finding Quasi-Shortest Path with Graph Coarsening
|
| 著者名 |
|
○Takeaki Iwata, Keita Kitaura, Ryotaro Matsuo, Hiroyuki Ohsaki,
|
| キーワード |
|
Graph coarsening, Quasi-Shortest Path, Large-scale graph, RM (Random Matching), Dijkstra's algorithm
|
| 抄録 |
|
Recently, a variety of large-scale data with a graph structure, such as communication networks and large-scale integrated circuits, have appeared and become widespread, and it is expected to be used for large-scale graphs to represent such data. On the other hand, various graph algorithms for analyzing graphs have difficulty in dealing with large-scale graphs.To solve the aforementioned problem, graph sparsification and graph coarsening, which are graph mining techniques, have been actively studied.We believe that the graph coarsening algorithm can be applied not only to complex problems such as node clustering and graph partitioning problems, but also to the shortest path problem on graphs. In this paper, we propose a quasi-shortest path algorithm QSPC (Quasi-Shortest Path algorithm with Coarsening), which uses a typical graph coarsening algorithm, for finding a quasi-shortest path that is a redundant path with 3--5 hops
|
| 本文pdf |
|
PDF download
|
