The message complexity of distributed graph optimization
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 986986 (Why is no real title available?)
- scientific article; zbMATH DE number 17538 (Why is no real title available?)
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
- A deterministic distributed 2-approximation for weighted vertex cover in \(O(\log N\log\varDelta/\log^2\log\varDelta)\) rounds
- A simple deterministic distributed MST algorithm with near-optimal time and message complexities
- A time- and message-optimal distributed algorithm for minimum spanning trees
- A trade-off between information and communication in broadcast protocols
- An Improved Distributed Algorithm for Maximal Independent Set
- An efficient distributed algorithm for constructing small dominating sets
- Analytical approach to parallel repetition
- Beep-and-sleep: message and energy efficient set cover
- Beep-and-sleep: message and energy efficient set cover
- Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
- Can We Break Symmetry with o(m) Communication?
- Communication Complexity
- Communication Complexity
- Communication complexity of approximate matching in distributed graphs
- Construction and impromptu repair of an MST in a distributed network with o(m) communication
- Derandomizing distributed algorithms with small messages: spanners and dominating set
- Deterministic (1+ 𝜀 )-approximate maximum matching with poly(1/ 𝜀 ) passes in the semi-streaming model and beyond
- Deterministic distributed dominating set approximation in the CONGEST model
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Distributed Maximal Independent Set using Small Messages
- Distributed Spanner Approximation
- Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
- Distributed (+1)-coloring via ultrafast graph shattering
- Distributed approximation of maximum independent set and maximum matching
- Distributed computation of large-scale graph problems
- Efficient randomized distributed coloring in CONGEST
- Fooling views: a new lower bound technique for distributed computations under congestion
- Hardness of Distributed Optimization
- Improved Distributed Approximate Matching
- Improved deterministic distributed matching via rounding
- Lessons from the congested clique applied to MapReduce
- Local computation: lower and upper bounds
- Low diameter graph decompositions
- Lower bounds on communication complexity in distributed computer networks
- Message lower bounds via efficient network synchronization
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Near-optimal clustering in the \(k\)-machine model
- New bounds on the classical and quantum communication complexity of some graph properties
- On colouring random graphs
- On the Complexity of Universal Leader Election
- On the complexity of local distributed graph problems
- On the concentration of the domination number of the random graph
- On the distributional complexity of disjointness
- On the domination number of a random graph
- On the existence of a factor of degree one of a connected random graph
- On the hardness of approximating minimum vertex cover
- On the power of the congested clique model
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Proof-labeling schemes: broadcast, unicast and in between
- Quadratic and near-quadratic lower bounds for the CONGEST model
- Random graphs.
- Rapid randomized pruning for fast greedy distributed algorithms
- Super-fast 3-ruling sets
- Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
- The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
- The Range of Topological Effects on Communication
- The locality of distributed symmetry breaking
- The locality of distributed symmetry breaking
- Tight Network Topology Dependent Bounds on Rounds of Communication
- Tight analysis of parallel randomized greedy MIS
- Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
- Topology matters in communication
- Toward optimal bounds in the congested clique, graph connectivity and MST
- What cannot be computed locally!
- When distributed computation is communication expensive
This page was built for publication: The message complexity of distributed graph optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906393)
