scientific article; zbMATH DE number 7561283

DOI10.4230/LIPICS.DISC.2018.31MaRDI QIDQ5090923zbMATH OpenFDO

Authors Mohsen Ghaffari, Jason Li

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1805.04764

zbMATH Keywords

mixing timerandom graphsdistributed graph algorithmsmulti-commodity routing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• New classes of distributed time complexity
• scientific article; zbMATH DE number 4050992
• Efficient distributed algorithms by using the archimedean time assumption
• Near-optimal scheduling of distributed algorithms
• Some distributed algorithms revisited
• Distributed MST and routing in almost mixing time
• New approaches to deriving parallel algorithms
• scientific article; zbMATH DE number 2107027
• Transience bounds for distributed algorithms

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 839542 (Why is no real title available?)
• A GENERAL PRAM SIMULATION SCHEME FOR CLUSTERED MACHINES
• A unified approach to models of synchronous parallel machines
• An efficient parallel solver for SDD linear systems
• Distributed Computing: A Locality-Sensitive Approach
• Distributed MST and routing in almost mixing time
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Distributed algorithms for random graphs
• Efficient PRAM simulation on a distributed memory machine
• Generalized preconditioning and undirected minimum-cost flow
• Parallel Prefix Computation
• Parallelism in random access machines
• The complexity of deterministic PRAM simulation on distributed memory machines
• The cover time of the giant component of a random graph
• The hyperring: a low-congestion deterministic data structure for distributed environments
• The probabilistic method
• Time Bounded Random Access Machines with Parallel Processing
• Xheal, localized self-healing using expanders

Cited in

(7)

• Low-congestion shortcut and graph parameters
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Distributed MST and routing in almost mixing time
• New classes of distributed time complexity
• A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time
• Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
• Deterministic near-optimal distributed listing of cliques

This page was built for publication:

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