Opin vísindi

Improved distributed algorithms for coloring interval graphs with application to multicoloring trees

Improved distributed algorithms for coloring interval graphs with application to multicoloring trees


Title: Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
Author: Halldórsson, Magnús M.   orcid.org/0000-0002-5774-8437
Konrad, Christian
Date: 2020-04
Language: English
Scope: 29-41
University/Institute: Háskólinn í Reykjavík
Reykjavik University
School: Tæknisvið (HR)
School of Technology (RU)
Department: Tölvunarfræðideild (HR)
School of Computer Science (RU)
ISSN: 0304-3975
1879-2294 (eISSN)
DOI: https://doi.org/10.1016/j.tcs.2018.11.028
Subject: Theoretical Computer Science; General Computer Science; Algorithms and Complexity; Distributed computing; Tölvunarfræði; Reiknirit
URI: https://hdl.handle.net/20.500.11815/2034

Show full item record

Citation:

Halldorsson, M. M., & Konrad, C. (2020). Improved distributed algorithms for coloring interval graphs with application to multicoloring trees. Theoretical Computer Science, 811, 29–41. https://doi.org/10.1016/j.tcs.2018.11.028

Abstract:

We give a distributed (1+eps)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O((1/eps) log* n) rounds. If nodes are aware of their interval representations, then the algorithm can be adapted to the CONGEST model using the same number of rounds. Prior to this work, only constant factor approximations using O(log* n) rounds were known. Linial's ring coloring lower bound implies that the dependency on log* n cannot be improved. We further prove that the dependency on 1/eps is also optimal. To obtain our CONGEST model algorithm, we develop a color rotation technique that may be of independent interest. We demonstrate that color rotations can also be applied to obtain a (1+eps)-approximate multicoloring of directed trees in O((1/eps)log* n) rounds.

Description:

Post-print (lokagerð höfundar)

Rights:

Post-print (lokagerð höfundar)

Files in this item

This item appears in the following Collection(s)