Distributed algorithms for random graphs

DOI10.1016/J.TCS.2015.08.037MaRDI QIDQ888436zbMATH OpenOpenAlexFDO

Authors Krzysztof Krzywdziński, Katarzyna Rybarczyk

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

matchingcolouringdistributed algorithmsdominating setindependent setrandom graphs

Mathematics Subject Classification ID

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

Recommendations

• A processor efficient MIS algorithm on random graphs
• Radio communication in random graphs
• Some simple distributed algorithms for sparse networks
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Simple distributed +1-coloring of graphs

Cites work

• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• An efficient distributed algorithm for constructing small dominating sets
• Arboricity and spanning-tree packing in random graphs with an application to load balancing
• Cliques in random graphs
• Constant-time distributed dominating set approximation
• Deterministic coin tossing with applications to optimal parallel list ranking
• Deterministic distributed vertex coloring in polylogarithmic time
• Diameters of Random Graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed deterministic edge coloring using bounded neighborhood independence
• Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
• Minimum dominating set approximation in graphs of bounded arboricity
• On the Complexity of Distributed Network Decomposition
• On the concentration of the domination number of the random graph
• On the distributed complexity of computing maximal matchings
• On the domination number of a random graph
• On the independence number of random graphs
• On tree census and the giant component in sparse random graphs
• Parallel Symmetry-Breaking in Sparse Graphs
• Some simple distributed algorithms for sparse networks
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• The diameter of sparse random graphs
• The diameter of sparse random graphs

Cited in

(15)

• scientific article; zbMATH DE number 7561283 (Why is no real title available?)
• Random graphs of Internet type and the generalised allocation scheme
• Random Node-Asynchronous Updates on Graphs
• Distributed strategies for generating weight-balanced and doubly stochastic digraphs
• scientific article; zbMATH DE number 6767551 (Why is no real title available?)
• Distributed Averaging With Random Network Graphs and Noises
• Distributed algebraic connectivity estimation for undirected graphs with upper and lower bounds
• Deterministic Decentralized Search in Random Graphs
• Distributed MIS in O( n) awake complexity
• A distributed algorithm for finding Hamiltonian cycles in random graphs in O( n) time
• Distributed MIS in O(log log n) Awake Complexity
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• GHS algorithm on a graph with random weights
• Towards a Study of Low-Complexity Graphs
• Distributed MST for constant diameter graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q888436)