ALGORITHMS FOR SOME GRAPH PROBLEMS ON A DISTRIBUTED COMPUTATIONAL MODEL

This paper presents distributed algorithms for some graph problems on a network model of computation. These graph problems include breadth-first and breadth-depth searches of graphs, recognition of directed acyclic graphs and strong connectedness, finding weights of all the shortest paths from a single source to all other nodes in a weighted directed acyclic graph, and analyzing activity networks. The results of computations (i. e. , the outputs) of all the algorithms but the algorithm for recognition of directed acyclic graphs are available in a distributed manner. For algorithms in such a computational model, two types of complexity measures are important. One is the time complexity, and the other is the message or communication complexity. Both of these complexities are obtained for each of the aforesaid distributed algorithms.