3 papers
cs.DC2021
The Complexity of Symmetry Breaking in Massive Graphs
Christian Konrad, Sriram V. Pemmaraju, Talal Riaz +1
The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related -ruling set problem, in…
cs.DC2017
Symmetry Breaking in the Congest Model: Time- and Message-Efficient Algorithms for Ruling Sets
Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju +2
We study local symmetry breaking problems in the CONGEST model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. A -rulin…
cs.DC2016
Using Read- Inequalities to Analyze a Distributed MIS Algorithm
Sriram Pemmaraju, Talal Riaz
Until recently, the fastest distributed MIS algorithm, even for simple graphs, e.g., unoriented trees has been the simple randomized algorithm discovered the 80s. This algorithm (c…