The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
From MaRDI portal
Publication:3769980
DOI10.1137/0216019zbMath0632.68065OpenAlexW2088374619MaRDI QIDQ3769980
Shmuel Zaks, Ephraim Korach, Shlomo Moran
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216019
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of software (68N99)
Related Items (13)
Improved deterministic leader election in diameter-two networks ⋮ Leader election in well-connected graphs ⋮ A fast distributed approximation algorithm for minimum spanning trees ⋮ Hundreds of impossibility results for distributed computing ⋮ Sublinear bounds for randomized leader election ⋮ A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms ⋮ The complexity of leader election in diameter-two networks ⋮ THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS ⋮ Communication algorithms with advice ⋮ Message lower bounds via efficient network synchronization ⋮ Optimal lower bounds for some distributed algorithms for a complete network of processors ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Sense of direction in distributed computing
This page was built for publication: The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
