LABELLINGS, ORIENTATIONS, AND GREEDY ALGORITHMS
Dr Jan van den Heuvel, Centre for Discrete and Applicable Mathematics, Department of Mathematics, London School of Economics

Abstract: Given a graph G with edge-weights w : E(G) --> { 1,2,3,... }, a feasible labelling is a vertex labelling f : V(G) --> { 0,1,2,... } such that for all edges uv we have | f(u) - f(v) | >= w(uv). And in particular we are interested in the span of the weighted graph, defined as the minimum over all feasible labellings of the maximal label used.

This kind of labelling is used in problems such as frequency assignment for large-scale radio networks.

We show that feasible labellings correspond to orientations on the edges of the graph; and finding the span is equivalent to finding orientations that satisfy a certain minimality condition. But this doesn't mean that algorithms to find `good' orientations cannot perform differently from similar algorithms to find `good' labellings.

We discuss some first attempts to design algorithms to find orientations of weighted graphs that would give `good' labellings. And we show some results from simulations comparing these algorithms and similar algorithms for weighted labellings.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 19 March 2001.

back