Distributed Maximal Independent Set using Small Messages
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Analysis of algorithms (68W40)
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
(37)- Distributed reconfiguration of maximal independent sets
- Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
- MIS on trees
- Super-fast 3-ruling sets
- Trading bit, message, and time complexity of distributed algorithms
- Using read-k inequalities to analyze a distributed MIS algorithm
- The locality of distributed symmetry breaking
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Distributed Reconfiguration of Maximal Independent Sets
- Distributed arboricity-dependent graph coloring via all-to-all communication
- Network Decomposition and Distributed Derandomization (Invited Paper)
- Maximal independent sets in multichannel radio networks
- Optimal dynamic distributed MIS
- Brief announcement: Using read-k inequalities to analyze a distributed MIS algorithm
- Distributed MIS via all-to-all communication
- Brief announcement: Symmetry breaking in the \textsc{Congest} model: time- and message-efficient algorithms for ruling sets
- Distributed Lower Bounds for Ruling Sets
- Distributed distance-r covering problems on sparse high-girth graphs
- Distributed distance-\(r\) covering problems on sparse high-girth graphs
- Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics
- The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
- Distributed MIS with Low Energy and Time Complexities
- Distributed Symmetry Breaking on Power Graphs via Sparsification
- Derandomizing local distributed algorithms under bandwidth restrictions
- Symmetry breaking in the Congest model: time- and message-efficient algorithms for ruling sets
- Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond
- The complexity of symmetry breaking in massive graphs
- Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
- Improved distributed approximations for maximum independent set
- Coloring fast without learning your neighbors' colors
- An optimal bit complexity randomized distributed MIS algorithm
- Self-stabilizing MIS computation in the beeping model
- The message complexity of distributed graph optimization
- Distributed symmetry breaking on power graphs via sparsification
- Brief announcement: Self-stabilizing MIS computation in the beeping model
- Generalising the maximum independent set algorithm via Boolean networks
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
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)
