AdHoc-NOW 2007 · 6th International Conference on Ad-Hoc Networks & Wireless, Morelia, Mexico, September 2007 · doi:10.1007/978-3-540-74823-6_6
We study the algorithmic problem of coordinating transmissions in a wireless network where radio interference constrains concurrent transmissions on wireless links. We focus on pairwise conflicts between the links; these can be described as a conflict graph. Associated with the conflict graph are two fundamental network coordination tasks: (a) finding a nonconflicting set of links with the maximum total weight, and (b) finding a link schedule with the minimum total length. Our work shows that two assumptions on the geometric structure of conflict graphs suffice to achieve polynomial-time constant-factor approximations: (i) bounded density of devices, and (ii) bounded range of interference. We also show that these assumptions are not sufficient to obtain a polynomial-time approximation scheme for either coordination task.
Evangelos Kranakis and Jaroslav Opatrny (Eds.): Ad-Hoc, Mobile, and Wireless Networks, 6th International Conference, ADHOC-NOW 2007, Morelia, Mexico, September 24–26, 2007, Proceedings, volume 4686 of Lecture Notes in Computer Science, pages 74–86, Springer, Berlin, 2007