Efficient Implementation of the Italiano Algorithms for Updating the Transitive Closure on Associative Parallel Processors

• Autorzy: Nepomniaschay A.
• Języki publikacji: EN

Abstrakty

EN

We propose a simple data structure for an efficient implementation of the Italiano algorithms for the dynamic updating of the transitive closure of a directed graph represented as adjacency matrix on a model of associative (or content addressable) parallel processors with vertical processing (the STAR–machine). Associative versions of the Italiano algorithms are represented as procedures DeleteArc1 and InsertArc1. We prove the correctness of these procedures and evaluate their time and space complexity. We also present the main advantages of associative versions of the Italiano algorithms.

Słowa kluczowe

EN

directed graphs; spanning tree; adjacency matrix; transitive closure of a directed graph; incremental algorithm; decremental algorithm; associative parallel processor; access data by contents

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 89, nr 2-3
• Strony: 313--329
• Opis fizyczny: bibliogr. 17 poz.

Twórcy

autor

Nepomniaschay A.

• Laboratory of parallel algorithms and structures, pr. Lavrentieva, 6, Novosibirsk, 630090, Russia,

Bibliografia

• [1] Fet, Y.: Parallel processing in cellular arrays, Taunton, UK, Research Studies Press, 1995.
• [2] Foster, C. C.: Content addressable parallel processors, New York, Van Nostrand Reinhold Company, 1976.
• [3] Frigioni, D., Miller, T., Nanni, U., Pasqualone, G., Schaefer, G., and Zaroliagis, C.: An experimental study of dynamic algorithms for directed graphs, Proc. of the European Symp. on Algorithms, Algorithms-ESA'98, LNCS 1461, Springer-Verlag, Berlin, 1998, 368-380.
• [4] Henzinger, M. R. and King, V.: Fully dynamic biconnectivity and transitive closure, Proc. 36th IEEE Symposium on Foundations of Computer Science, (FOCS'95), IEEE Computer Society, 1995, 664-672.
• [5] Ibaraki, T., Katoh, N.: On-line computation of transitive closure for graphs, Information Processing Letters, 16, 1983, 95-97.
• [6] Italiano, G. F.: Amortized efficiency of a path retrieval data structure, Theoretical Computer Science, 48 (2-3), 1986, 273-281.
• [7] Italiano, G. F.: Finding paths and deleting edges in directed acyclic graphs, Information Processing Letters, 28, 1988, 5-11.
• [8] Nepomniaschaya, A. S.: Language STAR for associative and parallel computation with vertical data processing, Proc. of the Intern. Conf. "Parallel Computing Technologies", Novosibirsk, Russia, World Scientific, Singapore, 1991, 258-265.
• [9] Nepomniaschaya, A. S.: Representation of the Gabow algorithm for finding smallest spanning trees with a degree constraint on associative parallel processors, Proc. Euro-Par'96 Parallel Processing, Second Intern. Euro-Par Conf., Lyon, France. LNCS 1128, Springer-Verlag, Berlin, 1996, 813-817.
• [10] Nepomniaschaya, A. S.: Solution of path probles using associative parallel processors, Proc. of the Intern. Conf. on Parallel and Distributed Systems, ICPADS'97, Seoul, Korea, IEEE Computer Society, 1997, 610-617.
• [11] Nepomniaschaya, A. S., Dvoskina, M.A.: A simple implementation of Dijkstra's shortest path algorithm on associative parallel processors, Fundamenta Informaticae, IOS Press, 43, 2000, 227-243.
• [12] Nepomniaschaya, A. S.: An associative version of the Bellman-Ford algorithm for finding the shortest paths in directed graphs, Proc. of the 6-th Intern. Conf. PaCT-2001, Novosibirsk, Russia, LNCS 2127, Springer-Verlag, Berlin, 2001, 285-292.
• [13] Nepomniaschaya, A. S.: Efficient implementation of Edmonds' algorithm for finding optimum branchings on associative parallel processors, Proc. of the Eighth Intern. Conf. on Parallel and Distributed Systems, ICPADS'01, KyongJu City, Korea, IEEE Computer Society, 2001, 3-8.
• [14] Nepomniaschaya, A. S.: Comparison of performing the Prim-Dijkstra algorithm and the Kruskal algorithm by means of associative parallel processors, Cybernetics and System Analysis, Kiev: Naukova Dumka, No. 2, 2000, 19-27 (in Russian, English translation by Plenum Press).
• [15] Nepomniaschaya, A. S.: Associative version of Italiano's decremental algorithm for the transitive closure problem, Proc. of the 9-th Intern. Conf., PaCT 2007, Pereslavl-Zalessky, Russia, LNCS 4671, Springer-Verlag, Berlin, 2007, 442-452.
• [16] La Poutré, J.A. and van Leeuwen, J.: Maintenance of transitive closure and transitive reduction of graphs, Proc. Workshop on Graph-Theoretic Conceps in Computer Science, LNCS 314, Springer-Verlag, Berlin, 1988, 106-120.
• [17] Yellin, D.M.: Speeding up dynamic transitive closure for bounded degree graphs, Acta Informatica, 30 (4), 1993, 369-384.