DocumentCode :
3323078
Title :
An Efficient Algorithm for Answering Graph Reachability Queries
Author :
Chen, Yangjun ; Chen, Yibin
Author_Institution :
Dept. Appl. Comput. Sci., Univ. of Winnipeg, Winnipeg, MB
fYear :
2008
fDate :
7-12 April 2008
Firstpage :
893
Lastpage :
902
Abstract :
Given a directed graph G, to check whether a node v is reachable from another node u through a path is often required. In a database system, such an operation is called a recursion computation or reachability checking and not efficiently supported. The reason for this is that the space to store the whole transitive closure of G is prohibitively high. In this paper, we address this issue and propose an 0(n2 + bnradic(b)) time algorithm to decompose a directed acyclic graph (DAG) into a minimized set of disjoint chains to facilitate reachability checking, where n is the number of the nodes and b is the DAG´s width, defined to be the size of a largest node subset U of the DAG such that for every pair of nodes u, v isin U, there does not exist a path from u to v or from v to u. Using this algorithm, we are able to label a graph in 0(be) time and store all the labels in O(bn) space with O(logb) reachability checking time, where e is the number of the edges of the DAG. The method can also be extended to handle cyclic directed graphs. Experiments have been performed, showing that our method is promising.
Keywords :
computational complexity; directed graphs; query processing; reachability analysis; database system; directed acyclic graph; graph reachability queries; reachability checking; recursion computation; Application software; CADCAM; Computer aided manufacturing; Computer aided software engineering; Computer science; Database systems; Deductive databases; Encoding; Navigation; Software systems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on
Conference_Location :
Cancun
Print_ISBN :
978-1-4244-1836-7
Electronic_ISBN :
978-1-4244-1837-4
Type :
conf
DOI :
10.1109/ICDE.2008.4497498
Filename :
4497498
Link To Document :
بازگشت