Network Decomposition and Distributed Derandomization (Invited Paper)

DOI10.1007/978-3-030-54921-3_1OpenAlexW3046572849MaRDI QIDQ5100942

Mohsen Ghaffari

Publication date: 1 September 2022

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-54921-3_1

zbMATH Keywords

derandomizationnetwork decompositiondistributed graph algorithmsLOCAL model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• Fast distributed network decompositions and covers
• A simple proof that finding a maximal independent set in a graph is in NC
• A fast and simple randomized parallel algorithm for maximal matching
• Private vs. common random bits in communication complexity
• Low diameter graph decompositions
• Improved distributed degree splitting and edge coloring
• Derandomizing local distributed algorithms under bandwidth restrictions
• On the Distributed Complexity of Computing Maximal Matchings
• On the complexity of distributed graph coloring with local minimality constraints
• The Locality of Distributed Symmetry Breaking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• An Improved Distributed Algorithm for Maximal Independent Set
• Distributed Degree Splitting, Edge Coloring, and Orientations
• Constructing a Maximal Independent Set in Parallel
• What Can be Computed Locally?
• On the complexity of local distributed graph problems
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set
• Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Deterministic Distributed Dominating Set Approximation in the CONGEST Model
• On the Use of Randomness in Local Distributed Graph Algorithms
• Deterministic distributed vertex coloring in polylogarithmic time
• Deterministic distributed edge-coloring with fewer colors
• An optimal distributed (Δ+1)-coloring algorithm?
• Distributed Maximal Independent Set using Small Messages
• A lower bound for the distributed Lovász local lemma
• Brief Announcement
• Distributed Strong Diameter Network Decomposition
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• How much does randomness help with locally checkable problems?

This page was built for publication: Network Decomposition and Distributed Derandomization (Invited Paper)