Algorithms for some graph problems on a distributed computational model (Q580985)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for some graph problems on a distributed computational model |
scientific article |
Statements
Algorithms for some graph problems on a distributed computational model (English)
0 references
1987
0 references
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 graphs, 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.
0 references
distributed algorithms
0 references
graph problems
0 references
network model of computation
0 references
complexity measures
0 references
time complexity
0 references
communication complexity
0 references