Improved distributed approximations for maximum independent set

DOI10.4230/lipics.disc.2020.35zbMATH Open1540.68188MaRDI QIDQ6535034

Seri Khoury, Aaron Schild, Gregory Schwartzman, Ken-ichi Kawarabayashi

Publication date: 2 November 2023

zbMATH Keywords

lower boundsapproximation algorithmsdistributed graph algorithms

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Computing large independent sets in a single round
• The Locality of Distributed Symmetry Breaking
• Fast Distributed Approximations in Planar Graphs
• Leveraging Linial’s Locality Limit
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• On the complexity of local distributed graph problems
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Hardness of Distributed Optimization
• Distributed Maximal Independent Set using Small Messages
• Brief Announcement
• Distributed Approximation of Maximum Independent Set and Maximum Matching
• A unified approach to approximating resource allocation and scheduling
• Simple and local independent set approximation
• Quadratic and near-quadratic lower bounds for the CONGEST model
• Derandomizing local distributed algorithms under bandwidth restrictions

Related Items (6)

A log-star distributed maximal independent set algorithm for growth-bounded graphs ⋮ An Improved Distributed Algorithm for Maximal Independent Set ⋮ Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ Distributed Maximal Independent Set using Small Messages ⋮ Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets

Recommendations

• Improved approximations for maximum independent set via approximation chains 👍 👎
• Distributed large independent sets in one round on bounded-independence graphs 👍 👎
• A new distributed approximation algorithm for the maximum weight independent set problem 👍 👎
• Distributed reconfiguration of maximal independent sets 👍 👎
• An Improved Distributed Algorithm for Maximal Independent Set 👍 👎
• Distributed Reconfiguration of Maximal Independent Sets 👍 👎
• Distributed Approximation of Maximum Independent Set and Maximum Matching 👍 👎
• Distributed Computing 👍 👎
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs 👍 👎
• Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set 👍 👎

This page was built for publication: Improved distributed approximations for maximum independent set