Distributed Coloring and the Local Structure of Unit-Disk Graphs

Autor: Arnaud de Mesmay, Louis Esperet, Sébastien Julliot
Přispěvatelé: Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Gąsieniec L., Klasing R., Radzik T., ANR-16-CE40-0009,GATO,Graphes, Algorithmes et TOpologie(2016), ANR-18-CE40-0032,GrR,Reconfiguration de Graphes(2018), ANR-19-CE40-0014,Min-Max,Constructions de min-max en géométrie et topologie(2019), ANR-11-LABX-0025,PERSYVAL-lab,Systemes et Algorithmes Pervasifs au confluent des mondes physique et numérique(2011)
Rok vydání: 2021
Předmět:
Computational Geometry (cs.CG)
FOS: Computer and information sciences
General Computer Science
Context (language use)
0102 computer and information sciences
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Omega
Theoretical Computer Science
Combinatorics
020204 information systems
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
FOS: Mathematics
0202 electrical engineering
electronic engineering
information engineering
Mathematics - Combinatorics
Graph coloring
Mathematics
Conjecture
Degree (graph theory)
Binary logarithm
Unit disk
Computer Science - Distributed
Parallel
and Cluster Computing
010201 computation theory & mathematics
Distributed algorithm
Computer Science - Computational Geometry
Distributed
Parallel
and Cluster Computing (cs.DC)
Combinatorics (math.CO)
MathematicsofComputing_DISCRETEMATHEMATICS
Zdroj: Algorithms for Sensor Systems ISBN: 9783030892395
ALGOSENSORS
ALGOSENSORS 2021
ALGOSENSORS 2021, Sep 2021, Lisbonne, Portugal. ⟨10.1007/978-3-030-89240-1_5⟩
Popis: Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph $G$ with at most $4\omega(G)$ colors, where $\omega(G)$ is the clique number of $G$. This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph $G$ with at most $5.68\omega(G)+1$ colors in $O(\log^* n)$ rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4\omega(G)$, which would imply the existence of a $O(\log n)$ round algorithm coloring any unit-disk graph $G$ with (approximately) $4\omega(G)$ colors in the LOCAL model. We provide partial results towards this conjecture using Fourier-analytical tools.
Comment: 25 pages, corrects a mistake in the proceedings version of the paper. A preliminary version of this work appeared in the proceedings of the 17th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS 2021)
Databáze: OpenAIRE
Externí odkaz: