Distributed Maximal Independent Set using Small Messages
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)
Recommendations
- Distributed Reconfiguration of Maximal Independent Sets
- Distributed reconfiguration of maximal independent sets
- An Improved Distributed Algorithm for Maximal Independent Set
- Improved distributed approximations for maximum independent set
- On the message complexity of distributed problems
- Loosely-stabilizing maximal independent set algorithms with unreliable communications
- Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
- Distributed approximation of maximum independent set and maximum matching
- Derandomizing distributed algorithms with small messages: spanners and dominating set
Cited in
(36)- Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Maximal independent sets in multichannel radio networks
- The complexity of symmetry breaking in massive graphs
- scientific article; zbMATH DE number 7561635 (Why is no real title available?)
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Brief announcement: Self-stabilizing MIS computation in the beeping model
- Derandomizing local distributed algorithms under bandwidth restrictions
- Generalising the maximum independent set algorithm via Boolean networks
- Brief announcement: Using read-k inequalities to analyze a distributed MIS algorithm
- The locality of distributed symmetry breaking
- MIS on trees
- Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
- Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- Trading bit, message, and time complexity of distributed algorithms
- Using read-k inequalities to analyze a distributed MIS algorithm
- Improved distributed approximations for maximum independent set
- Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
- Self-stabilizing MIS computation in the beeping model
- Optimal dynamic distributed MIS
- Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
- Distributed distance-r covering problems on sparse high-girth graphs
- Distributed MIS with Low Energy and Time Complexities
- Distributed Symmetry Breaking on Power Graphs via Sparsification
- The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
- Distributed MIS via all-to-all communication
- An optimal bit complexity randomized distributed MIS algorithm
- Distributed Lower Bounds for Ruling Sets
- Super-fast 3-ruling sets
- Distributed reconfiguration of maximal independent sets
- The message complexity of distributed graph optimization
- Distributed symmetry breaking on power graphs via sparsification
- Coloring fast without learning your neighbors' colors
- Network Decomposition and Distributed Derandomization (Invited Paper)
This page was built for publication: Distributed Maximal Independent Set using Small Messages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236233)
