Distributed Reconfiguration of Maximal Independent Sets

DOI10.4230/LIPIcs.ICALP.2019.135OpenAlexW2966791356MaRDI QIDQ5092338

Mikaël Rabie, Keren Censor-Hillel

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10711/pdf/LIPIcs-ICALP-2019-135.pdf/

zbMATH Keywords

maximal independent setreconfigurationdistributed graph algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• Unnamed Item
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• Complexity of independent set reconfigurability problems
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• The complexity of change
• Super-Fast 3-Ruling Sets.
• Local Computation
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• An Improved Distributed Algorithm for Maximal Independent Set
• On the Complexity of Distributed Network Decomposition
• Distributed Recoloring
• Locally-Iterative Distributed (Δ+ 1)
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time

This page was built for publication: Distributed Reconfiguration of Maximal Independent Sets