DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2022.8

Simple Streaming Algorithms for Edge Coloring

Authors: Mohammad Ansari, Mohammad Saneian, and Hamid Zarrabi-Zadeh

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

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 Õ(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.

Cite as

Mohammad Ansari, Mohammad Saneian, and Hamid Zarrabi-Zadeh. Simple Streaming Algorithms for Edge Coloring. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 8:1-8:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ESA.2022.8},
  URN =		{urn:nbn:de:0030-drops-169468},
  doi =		{10.4230/LIPIcs.ESA.2022.8},
  annote =	{Keywords: Edge coloring, streaming model, adversarial order}
}

Search Results

Documents authored by Ansari, Mohammad

Simple Streaming Algorithms for Edge Coloring

Abstract

Cite as

Thanks for your feedback!

Could not send message