Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST

DOI10.1145/3382734.3405702MaRDI QIDQ5854059zbMATH OpenOpenAlexFDO

Authors Yuval Efron, Ofer Grossman, Seri Khoury

Publication date 15 March 2021

Published in Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.07427

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited in

(3)

• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• The message complexity of distributed graph optimization
• Improved hardness of approximation of diameter in the CONGEST model

This page was built for publication: Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST

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