Back to Search
Start Over
Radio aggregation scheduling.
- Source :
-
Theoretical Computer Science . Nov2020, Vol. 840, p143-153. 11p. - Publication Year :
- 2020
-
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 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]
- Subjects :
- *ALGORITHMS
*TREE graphs
*SPANNING trees
*RADIO networks
*RADIOS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 840
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 145755667
- Full Text :
- https://doi.org/10.1016/j.tcs.2020.07.032