Brief Announcement

DOI10.1145/3087801.3087865zbMath1380.68433arXiv1705.07861OpenAlexW2737971506MaRDI QIDQ5368965

Gopal Pandurangan, Talal Riaz, Shreyas Pai, Peter Robinson, Sriram V. Pemmaraju

Publication date: 11 October 2017

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

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

zbMATH Keywords

symmetry breakinglocal modelmaximal independent setround complexitymessage complexityruling setsCongest model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (3)

Fooling views: a new lower bound technique for distributed computations under congestion ⋮ The complexity of leader election in diameter-two networks ⋮ Distributed Lower Bounds for Ruling Sets

This page was built for publication: Brief Announcement