Distributed algorithms for random graphs

DOI10.1016/j.tcs.2015.08.037zbMath1330.68341OpenAlexW1250011919MaRDI QIDQ888436

Katarzyna Rybarczyk, Krzysztof Krzywdziński

Publication date: 30 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.08.037

zbMATH Keywords

matchingcolouringrandom graphsindependent setdominating setdistributed algorithms

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (4)

GHS algorithm on a graph with random weights ⋮ Distributed MIS in O(log log n) Awake Complexity ⋮ Unnamed Item ⋮ A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time

Cites Work

• Unnamed Item
• Unnamed Item
• On the independence number of random graphs
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• On the Distributed Complexity of Computing Maximal Matchings
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Parallel Symmetry-Breaking in Sparse Graphs
• Diameters of Random Graphs
• On tree census and the giant component in sparse random graphs
• Cliques in random graphs
• Distributed Computing: A Locality-Sensitive Approach
• On the Complexity of Distributed Network Decomposition
• The Diameter of Sparse Random Graphs
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Some simple distributed algorithms for sparse networks
• An efficient distributed algorithm for constructing small dominating sets
• Arboricity and spanning-tree packing in random graphs with an application to load balancing
• Deterministic Distributed Vertex Coloring in Polylogarithmic Time
• On the Concentration of the Domination Number of the Random Graph
• Constant-time distributed dominating set approximation
• Distributed deterministic edge coloring using bounded neighborhood independence
• The diameter of sparse random graphs
• On the domination number of a random graph

This page was built for publication: Distributed algorithms for random graphs