A Distributed Algorithm for Minimum-Weight Spanning Trees
From MaRDI portal
Publication:3964023
DOI10.1145/357195.357200zbMath0498.68040OpenAlexW2077371116WikidataQ55896377 ScholiaQ55896377MaRDI QIDQ3964023
Robert G. Gallager, Pierre A. Humblet, P. M. Spira
Publication date: 1983
Published in: ACM Transactions on Programming Languages and Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/357195.357200
Related Items (only showing first 100 items - show all)
Learning Coefficient Heterogeneity over Networks: A Distributed Spanning-Tree-Based Fused-Lasso Regression ⋮ A tree-based distributed method for cooperative flow field estimation ⋮ Distributed MIS with Low Energy and Time Complexities ⋮ Latency, capacity, and distributed minimum spanning trees ⋮ Distributed Bayesian: A Continuous Distributed Constraint Optimization Problem Solver ⋮ Parallel and Distributed Algorithms in P Systems ⋮ Game-theoretic fairness meets multi-party protocols: the case of leader election ⋮ On the impact of sense of direction on message complexity ⋮ A fully distributed (minimal) spanning tree algorithm ⋮ Distributed Broadcast Revisited: Towards Universal Optimality ⋮ Optimal cost-sensitive distributed minimum spanning tree algorithm ⋮ Proof labeling schemes ⋮ A principle for sequential reasoning about distributed algorithms ⋮ An improved algorithm for finding the median distributively ⋮ A survey of combinatorial optimization problems in multicast routing ⋮ Optimal fault-tolerant distributed construction of a spanning forest ⋮ A faster distributed protocol for constructing a minimum spanning tree ⋮ A mechanical proof of Segall's PIF algorithm ⋮ Parallel \((\Delta +1)\)-coloring of constant-degree graphs ⋮ Petri net based verification of distributed algorithms: An example ⋮ On temporal graph exploration ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ On the complexity of some arborescences finding problems on a multishop radio network ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ A distributed methodology for approximate uniform global minimum sharing ⋮ GHS algorithm on a graph with random weights ⋮ Local MST computation with short advice ⋮ The local detection paradigm and its applications to self-stabilization ⋮ Improved deterministic leader election in diameter-two networks ⋮ A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment ⋮ On risk-averse maximum weighted subgraph problems ⋮ A uniform self-stabilizing minimum diameter spanning tree algorithm ⋮ Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony ⋮ Distributed Disaster Disclosure ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Self-stabilizing minimum degree spanning tree within one from the optimal degree ⋮ A distributed approximation algorithm for the minimum degree minimum weight spanning trees ⋮ Leader election in well-connected graphs ⋮ An efficient distributed algorithm for maximum matching in general graphs ⋮ A theorem on atomicity in distributed algorithms ⋮ Distributed verification of minimum spanning trees ⋮ A fast distributed approximation algorithm for minimum spanning trees ⋮ A distributed shortest path algorithm for a planar network ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Efficient algorithms for optimistic crash recovery ⋮ Interval routing schemes allow broadcasting with linear message-complexity ⋮ A linear-time optimal-message distributed algorithm for minimum spanning trees ⋮ Sublinear bounds for randomized leader election ⋮ A ZONAL ALGORITHM FOR CLUSTERING AN HOC NETWORKS ⋮ A knowledge-based analysis of global function computation ⋮ Map construction of unknown graphs by multiple agents ⋮ A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms ⋮ Clustering the wireless ad hoc networks: a distributed learning automata approach ⋮ Maximum metric spanning tree made Byzantine tolerant ⋮ Distributed processing of graphs: Fundamental cycles algorithm ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds ⋮ Distributed event algebras ⋮ Low-congestion shortcut and graph parameters ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS ⋮ A fast minimum spanning tree algorithm based on \(K\)-means ⋮ Move-optimal gossiping among mobile agents ⋮ Bounded approximate decentralised coordination via the max-sum algorithm ⋮ Finding minimum weight connected dominating set in stochastic graph based on learning automata ⋮ On the message complexity of distributed problems ⋮ A distributed dual ascent algorithm for Steiner problems in multicast routing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ The power of multimedia: Combining point-to-point and multi-access networks ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ LEARNING AUTOMATA-BASED ALGORITHMS FOR FINDING MINIMUM WEAKLY CONNECTED DOMINATING SET IN STOCHASTIC GRAPHS ⋮ From reaction-diffusion to physarum computing ⋮ Distributed balanced color assignment on arbitrary networks ⋮ Message lower bounds via efficient network synchronization ⋮ An efficient distributed algorithm for finding all hinge vertices in networks ⋮ A parallel algorithm for finding a blocking flow in an acyclic network ⋮ Distributed MST for constant diameter graphs ⋮ Labeling schemes for tree representation ⋮ Growing spanning trees in plasmodium machines ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Optimal lower bounds for some distributed algorithms for a complete network of processors ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ Simple and efficient network decomposition and synchronization ⋮ A survey on interval routing ⋮ Scheduling in synchronous networks and the greedy algorithm ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ An adaptive and cost-optimal parallel algorithm for minimum spanning trees ⋮ The Steiner problem in distributed computing systems ⋮ An optimal distributed algorithm for recognizing mesh-connected networks ⋮ Introduction to local certification ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming ⋮ Sense of direction in distributed computing
This page was built for publication: A Distributed Algorithm for Minimum-Weight Spanning Trees
