Sublinear Algorithms for (Δ + 1) Vertex Coloring
From MaRDI portal
Publication:5236231
DOI10.1137/1.9781611975482.48zbMath1431.68174arXiv1807.08886OpenAlexW4253069973MaRDI QIDQ5236231
Sanjeev Khanna, Yu Chen, Sepehr Assadi
Publication date: 15 October 2019
Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.08886
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (16)
Equivalence classes and conditional hardness in massively parallel computations ⋮ A Framework for Adversarially Robust Streaming Algorithms ⋮ Revisiting maximum satisfiability and related problems in data streams ⋮ Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Revisiting maximum satisfiability and related problems in data streams ⋮ Distributed coloring of hypergraphs ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Single-pass streaming algorithms to partition graphs into few forests ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
This page was built for publication: Sublinear Algorithms for (Δ + 1) Vertex Coloring