FLS: A Labeling Scheme To Solve The Reachability Problem Of Dynamic Updating Graph

Testing reachability between nodes in a graph is a well-known problem with many important applications,including knowledge representation,program analysis, geographic navigation,Internet routing,ontology queries based on RDF/OWL,and metabolic network,as well as XML indexing.A naive method is to find the shortest path,which will take O(m) time,where m = |E|(number of edges).But this is apparently too slow for large graphs.Another naive method is to precompute the reachability between every pair of nodes - in other words,to compute and store the transitive closure of the graph.Then, a reachability query can be answered in constant time.However,this requires O(n~2) space,which makes it impractical for massive graphs.And,it is unable to effectively support the dynamic update of graph.The other existing graph reachability algorithm includes 2-HOP,HOPI and Dual Labeling,but they do not support graph update,and the time complexity and the space complexity of the first two algorithms are too large to use in the real application.Various approaches have been proposed to encode graph reachability information using node labeling schemes,but they are all unable to effectively support the dynamic update of graph.In this paper,we propose a novel approach called FLS (Fractional Labeling Scheme) to solve this problem,and corresponding algorithms. We also prove some theorems that present analytical results.A notable feature of FLS is that it uses the unlimited partition nature of fraction number to support fully update of the graph.For the update,only a few simple operations are needed.