Simple Streaming Algorithms for Edge Coloring

Authors Mohammad Ansari, Mohammad Saneian, Hamid Zarrabi-Zadeh



PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.8.pdf
  • Filesize: 483 kB
  • 4 pages

Document Identifiers

Author Details

Mohammad Ansari
  • Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
Mohammad Saneian
  • Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
Hamid Zarrabi-Zadeh
  • Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ESA.2022.8

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Graph coloring
Keywords
  • Edge coloring
  • streaming model
  • adversarial order

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Eshrat Arjomandi. An efficient algorithm for colouring the edges of a graph with Δ + 1 colours. Information Systems and Operational Research, 20(2):82-101, 1982. Google Scholar
  2. Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani. Online graph edge-coloring in the random-order arrival model. Theory of Computing, 8(1):567-595, 2012. Google Scholar
  3. Amotz Bar-Noy, Rajeev Motwani, and Joseph Naor. The greedy algorithm is optimal for on-line edge coloring. Information Processing Letters, 44(5):251-253, 1992. Google Scholar
  4. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. Streaming and massively parallel algorithms for edge coloring. In Proceedings of the 27th European Symposium on Algorithms, volume 144 of LIPIcs, pages 15:1-15:14, 2019. Google Scholar
  5. Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc. Online edge coloring algorithms via the nibble method. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, pages 2830-2842, 2021. Google Scholar
  6. Moses Charikar and Paul Liu. Improved algorithms for edge colouring in the W-streaming model. In Proceedings of the 4th SIAM Symposium on Simplicity in Algorithms, pages 181-183, 2021. Google Scholar
  7. Ilan Reuven Cohen, Binghui Peng, and David Wajc. Tight bounds for online edge coloring. In Proceedings of the 60th IEEE Symposium on Foundations of Computer Science, pages 1-25, 2019. Google Scholar
  8. Camil Demetrescu, Irene Finocchi, and Andrea Ribichini. Trading off space for passes in graph streaming problems. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pages 714-723, 2006. Google Scholar
  9. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. On graph problems in a semi-streaming model. In Proceedings of the 31st International Colloquium on Automata, Languages, and Programming, volume 3142 of LNCS, pages 531-543, 2004. Google Scholar
  10. Ian Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718-720, 1981. Google Scholar
  11. Jayadev Misra and David Gries. A constructive proof of Vizing’s theorem. Information Processing Letters, 41(3):131-133, 1992. Google Scholar
  12. Amin Saberi and David Wajc. The greedy algorithm is not optimal for on-line edge coloring. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, volume 198 of LIPIcs, pages 109:1-109:18, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail