An Algorithm for All-Pairs Regular Path Problem on External Memory Graphs
| Autor: | Kosetsu Ikeda, Yeondae Kwon, Nobutaka Suzuki |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Induced path Computer science 02 engineering and technology Hamiltonian path Longest path problem Widest path problem Combinatorics Indifference graph symbols.namesake Pathwidth Artificial Intelligence Hardware and Architecture 020204 information systems Shortest path problem 0202 electrical engineering electronic engineering information engineering symbols 020201 artificial intelligence & image processing Computer Vision and Pattern Recognition Electrical and Electronic Engineering Software Hamiltonian path problem |
| Zdroj: | IEICE transactions on information and systems. (4):944-958 |
| ISSN: | 0916-8532 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|