Efficiently Answering Minimum Reachable Label Set Queries in Edge-Labeled Graphs
Publication Name
International Conference on Information and Knowledge Management, Proceedings
Abstract
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.
Open Access Status
This publication is not available as open access
First Page
4585
Last Page
4589
Funding Number
61976187
Funding Sponsor
National Natural Science Foundation of China