LIPIcs.ESA.2022.8.pdf
- Filesize: 483 kB
- 4 pages
Document
Simple Streaming Algorithms for Edge Coloring
Authors
-
Part of:
Volume:
30th Annual European Symposium on Algorithms (ESA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-01
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
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)
0PDF Downloads
References
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Ian Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718-720, 1981.
-
Jayadev Misra and David Gries. A constructive proof of Vizing’s theorem. Information Processing Letters, 41(3):131-133, 1992.
-
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.