Fast recursive data processing in graphs using reduction
J.H. ter Bekke and J.A. Bakker
This paper presents an algorithm for recursive data processing in directed graphs. The proposed algorithm applies graph reduction in order to determine both starting points and a correct ordering of recursive operations, provided the directed graph is a-cyclic. Therefore it is essential that the algorithm is also able to detect cycles efficiently. The algorithm arose from the implementation of recursive, semantic query specifications and is implemented in a DBMS prototype. Experiments confirmed that the theoretically estimated time complexity is O(dN), where N is the number of arcs and d is the depth of the graph (d œ N). The worst-case performance is O(N2), also for cycle detection.
Keywords: graph algorithm, longest path, recursion, query language, expressive power, semantic modeling.
Proceedings of the 21st IASTED International Conference Applied Informatics February 10-13, Innsbruck, Austria, paper number 378-146, pages 490-494
From the conference proceedings:
Full paper in pdf-format [1049 KB]
From the personal digital library:
Full paper in pdf-format [46 KB]