Local computation of maximal independent set

DOI10.1109/FOCS54457.2022.00049MaRDI QIDQ6943045zbMATH OpenFDO

Authors Mohsen Ghaffari

Publication date 15 August 2025

Full work available at URL https://doi.org/10.1109/FOCS54457.2022.00049

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(7)

• Distributed symmetry breaking on power graphs via sparsification
• Generalising the maximum independent set algorithm via Boolean networks
• Locally computing edge orientations
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
• Local computation algorithms for knapsack: impossibility results, and how to avoid them
• A fast coloring oracle for average case hypergraphs
• A 0.51-approximation of maximum matching in sublinear \(n^{1.5}\) time

This page was built for publication: Local computation of maximal independent set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6943045)