License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.15
URN: urn:nbn:de:0030-drops-111361
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11136/
Behnezhad, Soheil ;
Derakhshan, Mahsa ;
Hajiaghayi, MohammadTaghi ;
Knittel, Marina ;
Saleh, Hamed
Streaming and Massively Parallel Algorithms for Edge Coloring
Abstract
A valid edge-coloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. (Note that the maximum degree, Delta, is a trivial lower bound.) In this paper, we revisit this fundamental problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model:
- Massively Parallel Computation: We give a randomized MPC algorithm that with high probability returns a Delta+O~(Delta^(3/4)) edge coloring in O(1) rounds using O(n) space per machine and O(m) total space. The space per machine can also be further improved to n^(1-Omega(1)) if Delta = n^Omega(1). Our algorithm improves upon a previous result of Harvey et al. [SPAA 2018].
- Graph Streaming: Since the output of edge-coloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors.
We give a one-pass O~(n)-space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors with high probability if the edges arrive in a random order. For adversarial order streams, we give another one-pass O~(n)-space algorithm that requires O(Delta^2) colors.
BibTeX - Entry
@InProceedings{behnezhad_et_al:LIPIcs:2019:11136,
author = {Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi and Marina Knittel and Hamed Saleh},
title = {{Streaming and Massively Parallel Algorithms for Edge Coloring}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {15:1--15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11136},
URN = {urn:nbn:de:0030-drops-111361},
doi = {10.4230/LIPIcs.ESA.2019.15},
annote = {Keywords: Massively Parallel Computation, Streaming, Edge Coloring}
}
|
Keywords: |
|
Massively Parallel Computation, Streaming, Edge Coloring |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
