Distributed coloring of hypergraphs

DOI10.1007/978-3-031-32733-9_5MaRDI QIDQ6188146zbMATH OpenFDO

Authors Duncan Adamson, Magnús M. Halldórsson, Alexandre Nolin

Publication date 11 January 2024

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

Full work available at URL https://doi.org/10.1007/978-3-031-32733-9_5

zbMATH Keywords

distributed computinghypergraph coloringcongested cliqueLOCAL 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

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• A constructive proof of the general Lovász local lemma
• A lower bound for the distributed Lovász local lemma
• A new technique for distributed symmetry breaking
• A time hierarchy theorem for the LOCAL model
• An Automatic Speedup Theorem for Distributed Problems
• An Improved Distributed Algorithm for Maximal Independent Set
• An exponential separation between randomized and deterministic complexity in the LOCAL model
• Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring
• Data streams: algorithms and applications.
• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• Deterministic (+1)-coloring in sublinear (in ) time in static, dynamic, and faulty networks
• Distributed (+1)-coloring via ultrafast graph shattering
• Distributed algorithms for the Lovász local lemma and graph coloring
• Distributed edge coloring and a special case of the constructive Lovász local lemma
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Distributed ∆-coloring plays hide-and-seek
• Linial for lists
• Locality in Distributed Graph Algorithms
• Near-optimal distributed degree+1 coloring
• On graph problems in a semi-streaming model
• Optimal deterministic routing and sorting on the congested clique
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• Sublinear algorithms for ( + 1) vertex coloring
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• The locality of distributed symmetry breaking

This page was built for publication: Distributed coloring of hypergraphs

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