A new distributed depth-first-search algorithm (Q1062756)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A new distributed depth-first-search algorithm
scientific article

    Statements

    A new distributed depth-first-search algorithm (English)
    0 references
    0 references
    1985
    0 references
    This paper presents a new distributed Depth-First-Search (DFS) algorithm for an asynchronous communication network, whose communication and time complexities are O(\(| E|)\) and O(\(| V|)\), respectively. The output of the algorithm is the DFS tree, kept in a distributed fashion. The existing algorithm, due to \textit{T.-Y. Cheung} [IEEE Trans. Software Eng. SE-9, 504-512 (1983; Zbl 0513.68066)], requires O(\(| E|)\) both in communication and time complexities.
    0 references
    distributed system
    0 references
    communication graph
    0 references
    time complexity
    0 references
    communication complexity
    0 references
    asynchronous communication network
    0 references

    Identifiers