学術雑誌論文 An Algorithm for All-Pairs Regular Path Problem on External Memory Graphs

SUZUKI, Nobutaka  ,  IKEDA, Kosetsu  ,  KWON, Yeondae

E99.D ( 4 )  , pp.944 - 958 , 2016-04 , 電子情報通信学会
ISSN:0916-8532
NII書誌ID(NCID):AA10826272
内容記述
In this paper, we consider solving the all-pairs regular path problem on large graphs efficiently. Let G be a graph and r be a regular path query, and consider finding the answers of r on G. If G is so small that it fits in main memory, it suffices to load entire G into main memory and traverse G to find paths matching r. However, if G is too large and cannot fit in main memory, we need another approach. In this paper, we propose a novel approach based on external memory algorithm. Our algorithm finds the answers matching r by scanning the node list of G sequentially. We made a small experiment, which suggests that our algorithm can solve the problem efficiently.
本文を読む

https://tsukuba.repo.nii.ac.jp/?action=repository_action_common_download&item_id=38404&item_no=1&attribute_id=17&file_no=1

このアイテムのアクセス数:  回

その他の情報