Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees

Magnús M. Halldórsson, Christian Konrad

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

226 Downloads (Pure)

Abstract

We give a distributed (1+)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O(1 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 [12]. Linial’s ring coloring lower bound implies that the dependency on log∗ n cannot be improved. We further prove that the dependency on 1 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 + )-approximate multicoloring of directed trees in O(1 log∗ n) rounds.
Original languageEnglish
Title of host publicationStructural Information and Communication Complexity
Subtitle of host publication24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers
EditorsShantanu Das, Sebastien Tixeuil
Pages247-262
Number of pages16
ISBN (Electronic)978-3-319-72050-0
DOIs
Publication statusPublished - 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
Volume10641
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint Dive into the research topics of 'Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees'. Together they form a unique fingerprint.

Cite this