Radio aggregation scheduling.

We consider the aggregation problem in radio networks: find a spanning tree in a given graph and a conflict-free schedule of the edges so as to minimize the latency of the computation. While a large body of literature exists on this and related problems, we give the first approximation results in graphs that are not induced by unit ranges in the plane. We give a polynomial-time O ˜ (d n) -approximation algorithm, where d is the average degree and n the number of vertices in the graph, and show that the problem is Ω (n 1 − ϵ) -hard (and Ω ((d n) 1 / 2 − ϵ) -hard) to approximate even on bipartite graphs, for any ϵ > 0 , rendering our algorithm essentially optimal. We also obtain a O (log ⁡ n) -approximation in interval graphs. [ABSTRACT FROM AUTHOR]