Online coloring and L

Prelegent(ci)

Konstanty Junosza-Szaniawski

Afiliacja

Politechnika Warszawska

Termin

9 marca 2017 12:15

Pokój

p. 5870

Tytuł w języku angielskim

2,1)-labeling of unit disk intersection graphs

Seminarium

Seminarium "Algorytmika"

---

We give a family of online algorithms for the classical coloring and the L(2,1)-labeling problems of unit disk intersection graphs. In the L(2,1)-labeling we ask for an assignment of non-negative integers to the vertices of the input graph, such that adjacent vertices get labels that differ by at least 2, and vertices with a common neighbor get different labels.
In particular, we present a coloring algorithm with competitive ratio less than 5, what makes it the currently best online coloring algorithm for unit disk intersection  graphs. Our algorithms make use of a geometric representation of such graphs and are inspired by previous results, but have better competitive ratios.  The improvement comes from a novel application of a  fractional and a b-fold coloring of the plane, which is in turn  a variation of the Hadwiger-Nelson problem. Our method can also be adapted successfully for other classes of geometric intersection graphs.

---