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
    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

    Identifiers