A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
From MaRDI portal
Publication:2456363
DOI10.1016/j.tcs.2007.05.028zbMath1125.68089OpenAlexW2161318588MaRDI QIDQ2456363
V. S. Anil Kumar, Gopal Pandurangan, Maleq Khan
Publication date: 18 October 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.028
probabilistic analysisminimum spanning treedistributed algorithmrandomized approximation algorithm\(k\)-connected spanning subgraph
Related Items (2)
A fast distributed approximation algorithm for minimum spanning trees ⋮ Xheal: a localized self-healing algorithm using expanders
Cites Work
- On the value of a random minimum spanning tree problem
- Asymptotics for Euclidean minimal spanning trees on random points
- Optimal lower bounds for some distributed algorithms for a complete network of processors
- Approximation algorithms for minimum-cost k-vertex connected subgraphs
- Approximation algorithm for k-node connected subgraphs via critical graphs
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Dynamic Steiner Tree Problem
- Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- Distributed Computing: A Locality-Sensitive Approach
- Some simple distributed algorithms for sparse networks
- Sub-linear distributed algorithms for sparse certificates and biconnected components
- Probability and Computing
- What cannot be computed locally!
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
