关键词: 可达性,K-Reach索引,优化算法

Abstract: The k-rechability problem is of great importance for newly emerged wireless and social network．The．latest proposed index K-Reach can quickly answer the problem of whether there exists a path of length less or equal than k between any pair of vertices．Notice that during the construction of the index,all vertices which are reachable by a computed vertex have been traversed,and the path information is recorded in the index．Therefore,an improved construction algorithm is proposed to avoid the repeated visiting of a large amount of vertices by making fully use of the path information of the computed vertices．Experiments based on a set of real-life data have demonstrated that the time complexity of the improved algorithm is significantly lower than the original construction algorithm.

Key words: Rechibility,K-Reach index,Algorithm optimization