Improved distributed approximations for maximum independent set
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Randomized algorithms (68W20) Approximation algorithms (68W25)
Recommendations
- An Improved Distributed Algorithm for Maximal Independent Set
- Distributed approximation of maximum independent set and maximum matching
- Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set
- A new distributed approximation algorithm for the maximum weight independent set problem
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Distributed Computing
- Distributed Reconfiguration of Maximal Independent Sets
- Distributed reconfiguration of maximal independent sets
- Improved approximations for maximum independent set via approximation chains
- Distributed large independent sets in one round on bounded-independence graphs
Cites work
- A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- A unified approach to approximating resource allocation and scheduling
- An Improved Distributed Algorithm for Maximal Independent Set
- Brief Announcement
- Computing large independent sets in a single round
- Derandomizing local distributed algorithms under bandwidth restrictions
- Distributed approximation of maximum independent set and maximum matching
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Maximal Independent Set using Small Messages
- Fast Distributed Approximations in Planar Graphs
- Hardness of Distributed Optimization
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- scientific article; zbMATH DE number 1833421 (Why is no real title available?)
- Leveraging Linial’s Locality Limit
- Locality in Distributed Graph Algorithms
- On the complexity of local distributed graph problems
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Quadratic and near-quadratic lower bounds for the CONGEST model
- Simple and local independent set approximation
- The locality of distributed symmetry breaking
Cited in
(10)- A new distributed approximation algorithm for the maximum weight independent set problem
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- An Improved Distributed Algorithm for Maximal Independent Set
- Distributed Maximal Independent Set using Small Messages
- Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
- Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set
- Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
- Local distributed rounding: generalized to MIS, matching, set cover, and beyond
- Distributed fractional local ratio and independent set approximation
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
This page was built for publication: Improved distributed approximations for maximum independent set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6535034)
