## Abstract

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 Õ (𝑑⎯⎯⎯𝑛‾‾‾√)

-approximation algorithm, where 𝑑⎯⎯⎯

is the average degree and n the number of vertices in the graph, and show that the problem is Ω(𝑛1−𝜖)

-hard (and Ω((𝑑⎯⎯⎯𝑛)1/2−𝜖)

-hard) to approximate even on bipartite graphs, for any 𝜖>0

, rendering our algorithm essentially optimal. We target geometrically defined graph classes, and in particular obtain a 𝑂(log𝑛)

-approximation in interval graphs.

-approximation algorithm, where 𝑑⎯⎯⎯

is the average degree and n the number of vertices in the graph, and show that the problem is Ω(𝑛1−𝜖)

-hard (and Ω((𝑑⎯⎯⎯𝑛)1/2−𝜖)

-hard) to approximate even on bipartite graphs, for any 𝜖>0

, rendering our algorithm essentially optimal. We target geometrically defined graph classes, and in particular obtain a 𝑂(log𝑛)

-approximation in interval graphs.

Original language | English |
---|---|

Title of host publication | Algorithms for Sensor Systems |

Subtitle of host publication | 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras, Greece, September 17-18, 2015, Revised Selected Papers |

Publisher | Springer, Cham |

Pages | 169-182 |

ISBN (Electronic) | 978-3-319-28472-9 |

ISBN (Print) | 978-3-319-28471-2 |

DOIs | |

Publication status | Published - 2016 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|