Efficient distributed algorithms solving problems about the connectivity of network

This paper presents new efficient distributed algorithms solving the following problems by using a depth first search tree on asynchronous network of processors connected via bidirectional links: the problem of finding the 2-connected components, the problem of finding the bridges and the problem of testing the 2-connectivity in undirected graph, and the problem of finding the strongly-connected components in directed graph. In all algorithms, the communications complexity is O(nlogn+e) and the ideal-time complexity is O(nG(n)), where n (resp. e) is the number of processors (resp. links) in the network. And, G(n) is the number of times that the log functions must be applied to n to get a result less than or equal to 1. Moreover, this paper presents that for above each problem the lower bound of the communication complexity is ¦[(e) and the lower bound of the ideal time complexity is ¦[(n). [In Japanese.]