Distributed algorithms for random graphs
From MaRDI portal
Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Recommendations
Cites work
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A Simple 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 deterministic edge coloring using bounded neighborhood independence
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
- scientific article; zbMATH DE number 986986 (Why is no real title available?)
- scientific article; zbMATH DE number 1139976 (Why is no real title available?)
- 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)- GHS algorithm on a graph with random weights
- Distributed algebraic connectivity estimation for undirected graphs with upper and lower bounds
- Deterministic Decentralized Search in Random Graphs
- Random graphs of Internet type and the generalised allocation scheme
- Towards a Study of Low-Complexity Graphs
- Distributed strategies for generating weight-balanced and doubly stochastic digraphs
- Distributed Averaging With Random Network Graphs and Noises
- scientific article; zbMATH DE number 7561283 (Why is no real title available?)
- Random Node-Asynchronous Updates on Graphs
- scientific article; zbMATH DE number 6767551 (Why is no real title available?)
- Distributed MST for constant diameter graphs
- 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
- Distributed MIS in O( n) awake complexity
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)
