License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.8
URN: urn:nbn:de:0030-drops-169468
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16946/
Go to the corresponding LIPIcs Volume Portal

Ansari, Mohammad ; Saneian, Mohammad ; Zarrabi-Zadeh, Hamid

Simple Streaming Algorithms for Edge Coloring

pdf-format:
LIPIcs-ESA-2022-8.pdf (0.5 MB)

Abstract

We revisit the classical edge coloring problem for general graphs in the streaming model. In this model, the input graph is presented as a stream of edges, and the algorithm must report colors assigned to the edges in a streaming fashion, using a memory of size O(n polylog n) on graphs of up to O(n²) edges. In ESA 2019 and SOSA 2021, two elegant randomized algorithms were presented for this problem in the adversarial edge arrival model, where the latest one colors any input graph using O(Δ²/s) colors with high probability in Õ(ns) space. In this short note, we propose two extremely simple streaming algorithms that achieve the same color and space bounds deterministically. Besides being surprisingly simple, our algorithms do not use randomness at all, and are very simple to analyze.

BibTeX - Entry

@InProceedings{ansari_et_al:LIPIcs.ESA.2022.8,
  author =	{Ansari, Mohammad and Saneian, Mohammad and Zarrabi-Zadeh, Hamid},
  title =	{{Simple Streaming Algorithms for Edge Coloring}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{8:1--8:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16946},
  URN =		{urn:nbn:de:0030-drops-169468},
  doi =		{10.4230/LIPIcs.ESA.2022.8},
  annote =	{Keywords: Edge coloring, streaming model, adversarial order}
}

Keywords: Edge coloring, streaming model, adversarial order
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI