Speeding up dynamic transitive closure for bounded degree graphs
Tóm tắt
Từ khóa
Tài liệu tham khảo
Aho, A., Hopcroft, J., Ullman, J.: The design and analysis of computer algorithms. Reading, Mass.: Addison Wesley 1974
Burke, M., Ryder, B.G.: Incremental iterative data flow analysis algorithms. Technical Report LCSR-TR-96, Rutgers University, Department of Computer Science, August 1987
Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structures persistent. J. Comput. System Sci.38 (1), 86?124 (1989)
Horspool, N.: Incremental generation of LR parsers. Technical report, University of Victoria, Computer Science Department, March 1988
Ibaraki, T., Katoh, N.: On-line computation of transitive closure of graphs. Inf. Process. Lett.16, 95?97 (1983)
Italiano, G.F.: Amortized efficiency of a path retrieval data structure. Theor. Comput. Sci.48, 273?281 (1986)
Italiano, G.F.: Finding paths and deleting edges in directed acyclic graphs. Inf. Process. Lett.28 (1), 13?19 (1988)
Italiano, G.F., Spaccamela, A.M., Nanni, U.: Dynamic data structures for series parallel digraphs. Columbia University, January 1989
Jagadish, H.V.: A compressed transitive closure technique for efficient fixed-point query processing. In: Proceedings of the Second International Conference on Expert Database Systems, Tysons Corner, VA, April 1988
La Poutre, J.A., van Leeuwen, J.: Maintenance of transitive closures and transitive reductions of graphs. In: Gottler, H., Schneider, H.J. (eds.) Graph-theoretic concepts in computer science 1987. (Lect. Notes Comput. Sci., vol. 314, pp. 106?120) Berlin Heidelberg New York: Springer 1988
Preparata, F.P., Tamassia, R.: Fully dynamic techniques for point location and transitive closure in planar structures. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, p. 558?567, 1988