Low-diameter graph decomposition is in NC

DOI10.1007/3-540-55706-7_8zbMath1502.68203OpenAlexW1846835234MaRDI QIDQ5056131

Baruch Awerbuch, Bonnie Berger, Lenore J. Cowen, David Peleg

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55706-7_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Generating sparse 2—spanners ⋮ Unnamed Item ⋮ Graph theoretical issues in computer networks

Cites Work

• Unnamed Item
• Competitive algorithms for distributed data management.
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Complexity of network synchronization
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• Sparser: A Paradigm for Running Distributed Algorithms
• Fast network decomposition

This page was built for publication: Low-diameter graph decomposition is in NC