The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors

DOI10.1137/0216019zbMATH Open0632.68065OpenAlexW2088374619MaRDI QIDQ3769980FDOQ3769980

Authors: Ephraim Korach, Shlomo Moran, Shmuel Zaks 

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

zbMATH Keywords

distributed algorithmcommunication complexityspanning treecomplete graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of software (68N99)

Cited In (13)

• Leader election in well-connected graphs
• Communication algorithms with advice
• Hundreds of impossibility results for distributed computing
• Message lower bounds via efficient network synchronization
• A fast distributed approximation algorithm for minimum spanning trees
• Message Lower Bounds via Efficient Network Synchronization
• Improved deterministic leader election in diameter-two networks
• Singularly optimal randomized leader election
• The complexity of leader election in diameter-two networks
• THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
• Sense of direction in distributed computing
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3769980)