Petteri Kaski · Aleksi Penttinen · Jukka Suomela

Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs

AdHoc-NOW 2007 · 6th International Conference on Ad-Hoc Networks & Wireless, Morelia, Mexico, September 2007 · doi:10.1007/978-3-540-74823-6_6

authors’ version publisher’s version

Abstract

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.

Publication

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

ISBN 978-3-540-74822-9

Links

Journal Version

© Springer 2007

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.