Sublinear Algorithms for (Δ + 1) Vertex Coloring

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

Mathematics Subject Classification ID

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