Distributed algorithms for random graphs
type: Item
instance of: scholarly article
title: Distributed algorithms for random graphs
zbMATH Open document ID: 1330.68341
published in: Theoretical Computer Science
publication date: 2015-10-30T00:00:00Z
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6502581
zbMATH Keywords: distributed algorithms
zbMATH Keywords: random graphs
zbMATH Keywords: colouring
zbMATH Keywords: independent set
zbMATH Keywords: dominating set
zbMATH Keywords: matching
author: Krzysztof Krzywdziński
author: Katarzyna Rybarczyk
MaRDI profile type: Publication
full work available at URL: j.tcs.2015.08.037
OpenAlex ID: W1250011919
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Q4385084
cites work: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
cites work: Deterministic Distributed Vertex Coloring in Polylogarithmic Time
cites work: Distributed deterministic edge coloring using bounded neighborhood independence
cites work: Distributed Graph Coloring: Fundamentals and Recent Developments
cites work: Cliques in random graphs
cites work: The diameter of sparse random graphs
cites work: Deterministic coin tossing with applications to optimal parallel list ranking
cites work: Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs
cites work: Q3122905
cites work: On the independence number of random graphs
cites work: Arboricity and spanning-tree packing in random graphs with an application to load balancing
cites work: On the Concentration of the Domination Number of the Random Graph
cites work: Parallel Symmetry-Breaking in Sparse Graphs
cites work: An efficient distributed algorithm for constructing small dominating sets
cites work: Diameters of Random Graphs
cites work: Constant-time distributed dominating set approximation
cites work: Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: On the distributed complexity of computing maximal matchings
cites work: Some simple distributed algorithms for sparse networks
cites work: On the Complexity of Distributed Network Decomposition
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: On tree census and the giant component in sparse random graphs
cites work: The Diameter of Sparse Random Graphs
cites work: On the domination number of a random graph
DOI: 10.1016/J.TCS.2015.08.037
description: scientific article; zbMATH DE number 6502581