A new distributed depth-first-search algorithm
From MaRDI portal
Publication:1062756
DOI10.1016/0020-0190(85)90083-3zbMath0573.68013OpenAlexW1990389251MaRDI QIDQ1062756
Publication date: 1985
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(85)90083-3
time complexitydistributed systemcommunication complexitycommunication graphasynchronous communication network
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of operating systems (68N25)
Related Items
Distributed Bayesian: A Continuous Distributed Constraint Optimization Problem Solver ⋮ An efficient distributed bridge-finding algorithm ⋮ Distributed algorithms for depth-first search ⋮ Upper and lower bounds for deterministic broadcast in powerline communication networks ⋮ Efficient distributed algorithms for single-source shortest paths and related problems on plane networks ⋮ Deterministic broadcasting time with partial knowledge of the network. ⋮ A note on the message complexity of Cidon's distributed depth-first search algorithm ⋮ DFS tree construction: Algorithms and characterizations ⋮ An efficient distributed algorithm for maximum matching in general graphs ⋮ Assigning labels in an unknown anonymous network with a leader ⋮ Deterministic broadcasting in ad hoc radio networks ⋮ Distributed processing of graphs: Fundamental cycles algorithm ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Recognition of DFS trees: Sequential and parallel algorithms with refined verifications ⋮ Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism ⋮ Algorithms for some graph problems on a distributed computational model ⋮ Compact distributed certification of planar graphs ⋮ Broadcasting in undirected ad hoc radio networks ⋮ Dynamic detection of subgraphs in computer networks ⋮ Time-Efficient Broadcast in Radio Networks ⋮ Some remarks on distributed depth-first search. ⋮ Self-stabilizing depth-first search
Cites Work
