Coloring edge-weighted (di)graphs

Graphs, Hypergraphs, and Computing

29 April 15:30 - 16:30

Magnus M. Halldorsson - Reykjavik University

Let D=(V,E,w) be a digraph with non-negative edge weights. For a vertex v and a vertex subset S, let d(S,v) = sum_{u \in S} w(u,v), i.e., the weighted in-degree of v, w.r.t. S. A subset S of vertices is said to be *independent* if d(S,v) < 1, for every v in S. This generalizes the classical independent sets in graphs, which correspond to the problem on 0/1-weighted graphs. A coloring is a partition of V into independent sets, as before.

The motivations for these problems lie in wireless networking, specifically scheduling problems under the so-called SINR model. While the norm in wireless studies is to assume that the weights are derived from points in a metric space, actual wireless settings are sufficiently unpredictable that it is valuable to explore the case of arbitrary digraphs.

We will present the few results that are known, but pose more open questions than we answer.

The collaborators that are or have been involved include Marijke Bodlaender, Christian Konrad, Pradipta Mitra, and Roger Wattenhofer.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to