Back to Search
Start Over
Efficient Processing of k-Hop Reachability Queries on Directed Graphs
- Source :
- Applied Sciences, Vol 13, Iss 6, p 3470 (2023)
- Publication Year :
- 2023
- Publisher :
- MDPI AG, 2023.
-
Abstract
- Given a directed graph, a k-hop reachability query, u→?kv, is used to check for the existence of a directed path from u to v that has a length of at most k. Addressing k-hop reachability queries is a fundamental task in graph theory and has been extensively investigated. However, existing algorithms can be inefficient when answering queries because they require costly graph traversal operations. To improve query performance, we propose an approach based on a vertex cover. We construct an index that covers all reachability information using a small set of vertices from the input graph. This allows us to answer k-hop reachability queries without performing graph traversal. We propose a linear-time algorithm to quickly compute a vertex cover, S, which we use to develop a novel labeling scheme and two algorithms for efficient query answering. The experimental results demonstrate that our approach significantly outperforms the existing approaches in terms of query response time.
Details
- Language :
- English
- ISSN :
- 20763417
- Volume :
- 13
- Issue :
- 6
- Database :
- Directory of Open Access Journals
- Journal :
- Applied Sciences
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.88c0b0b7f2444f1f8884b4b8ad0f68f3
- Document Type :
- article
- Full Text :
- https://doi.org/10.3390/app13063470