The complexity of symmetry breaking in massive graphs

DOI10.4230/lipics.disc.2019.26zbMath1515.68248MaRDI QIDQ6487543

Peter Robinson, Christian Konrad, Talal Riaz, Sriram V. Pemmaraju

Publication date: 3 February 2023

zbMATH Keywords

information theorycommunication complexitystreaming algorithmsmaximal independent setruling setk-machine model

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27) Communication complexity, information complexity (68Q11)

Related Items (1)

Near-optimal clustering in the \(k\)-machine model

This page was built for publication: The complexity of symmetry breaking in massive graphs