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.DISC.2019.36
URN: urn:nbn:de:0030-drops-113438
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11343/
Behnezhad, Soheil ;
Derakhshan, Mahsa ;
Hajiaghayi, MohammadTaghi ;
Knittel, Marina ;
Saleh, Hamed
Brief Announcement: 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. In this paper, we revisit this 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 w.h.p., returns a (1+o(1))Delta 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)}. This is, to our knowledge, the first constant round algorithm for a natural graph problem in the strongly sublinear regime of MPC. Our algorithm improves a previous result of Harvey et al. [SPAA 2018] which required n^{1+Omega(1)} space to achieve the same result.
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 w.h.p., 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:11343,
author = {Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi and Marina Knittel and Hamed Saleh},
title = {{Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring}},
booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)},
pages = {36:1--36:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-126-9},
ISSN = {1868-8969},
year = {2019},
volume = {146},
editor = {Jukka Suomela},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11343},
URN = {urn:nbn:de:0030-drops-113438},
doi = {10.4230/LIPIcs.DISC.2019.36},
annote = {Keywords: Massively Parallel Computation, Streaming, Edge Coloring}
}
|
Keywords: |
|
Massively Parallel Computation, Streaming, Edge Coloring |
|
Collection: |
|
33rd International Symposium on Distributed Computing (DISC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
08.10.2019 |
