Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs
- Publisher:
- ACM
- Publication Type:
- Conference Proceeding
- Citation:
- International Conference on Information and Knowledge Management, Proceedings, 2022, pp. 4585-4589
- Issue Date:
- 2022-10-17
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
[CIKM 2022] Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs.pdf | Published version | 1.83 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
The reachability query is a fundamental problem in graph analysis. Recently, many studies focus on label-constraint reachability queries, which tries to verify whether two vertices are reachable under a given label set. However, in many real-life applications, it is more practical to find the minimum label set required to ensure the reachability of two vertices, which is neglected by previous research. To fill the gap, in this paper, we propose and investigate the minimum reachable label set (MRLS) problem in edge-labeled graphs. Specifically, given an edge-labeled graph and two vertices s, t, the MRLS problem aims to find a label set L with the minimum size such that s can reach t through L. We prove the hardness of our problem, and develop different optimization strategies to improve the scalability of the algorithms. Extensive experiments on 6 datasets demonstrate the advantages of the proposed algorithms.
Please use this identifier to cite or link to this item: