Reachability Algorithm Based on Key Points Labeling for Sparse Graphs. (English)

Reachability queries of directed graphs are fundamental when studying various network problems, such as querying whether two persons follow each other in a social network. However, with the increasing size of networks, traditional algorithms have become unacceptable due to their huge time or space complexity. Therefore, it is necessary to use a suitable reachability algorithm according to the structural characteristics of the network. A sparse graph consists of several directed spanning trees with a small number of non-tree edges. The GRKPL (graph reachability indexing via key points labeling) algorithm splits the reachability problem in sparse graphs into two parts: the tree reachability problem and the impact of adding non-tree edges. The first part is solved by the interval labeling method, and the second part is solved by constructing a key point set, which transforms all the reachability queries in the original graph into queries in the key point set. The key point set includes all nodes covered by nontree edges and the lowest common ancestors between adjacent nodes after these nodes are sorted in the preorder traversal order. And it is proven that the size of the key point set is of the same order of magnitude as the size of the non-tree edges in the original graph. Finally, GRKPL is tested on ten small- and medium-scale and four large-scale realistic datasets. GRKPL performs well on small- and medium-scale datasets, with an average 49.8% reduction in query processing time and 65.1% reduction in space occupation compared to other algorithms. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Frontiers of Computer Science & Technology is the property of Beijing Journal of Computer Engineering & Applications Journal Co Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)