Wireless Publications

Link Capacity and Scheduling

• Universal Framework for Wireless Scheduling Problems (with Tigran Tonoyan)
  ICALP, to appear, July 2017. Received Best paper award at Track C. Invited to Highlights on Algorithms, June 2018.
• Wireless Link Capacity under Shadowing and Fading (with Tigran Tonoyan). June 2017. In MobiHoc 2017.
• The Power of Non-Uniform Wireless Power (with Stephan Holzer, Pradipta Mitra and Roger Wattenhofer)
  SIAM Journal of Computing, 46(3):1062--1098, June 2017
• The Price of Local Power Control in Wireless Scheduling (with Tigran Tonoyan).
  FSTTCS'15, full version, Feb 2015.
• Limitations of Current Wireless Scheduling Algorithms (with Tigran Tonoyan).
  ALGOSENSORS'15 Part of arXiv:1502.05279
• A Note on Vertex Coloring Edge-Weighted Digraphs (with Joergen Bang-Jensen)
  Mittag-Leffler Report No. 29, 2013/2014, spring. Information Processing Letters, 115(10):791-796, October 2015.
• How Well Can Graphs Represent Wireless Interference? (with Tigran Tonoyan)
  STOC '15
  Full version on arXiv
• Progress (and Lack Thereof) for Graph Coloring Approximation Problems
  SOFSEM'15 (invited paper), Jan 2015
• Beyond Geometry : Towards Fully Realistic Wireless Models (with Marijke Bodlaender)
  PODC'14
• Algorithms for Wireless Capacity (with Olga Goussevskaia and Roger Wattenhofer).
  IEEE/ACM Transactions on Networking, June 2014. A note on precedence and credit.
  This paper incorporates (and corrects) the results in the two papers "Capacity of Arbitrary Wireless Networks" and "Wireless Communication is in APX".
• Wireless capacity with arbitrary gain matrix (with Pradipta Mitra)
  Theoretical Computer Science 553:57--63, October 2014. Preliminary version appears in ALGOSENSORS'11.
• Wireless scheduling with power control
  ACM Transactions on Algorithms, Dec 2013. Preliminary version appeared in ESA'09
• The Power of Non-Uniform Wireless Power (with Stephan Holzer, Pradipta Mitra and Roger Wattenhofer)
  SODA'13, full version
• Wireless Capacity and Admission Control in Cognitive Radio (with Pradipta Mitra). arxiv.org/abs/1111.5200.
  Infocom '12
• Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model (with Pradipta Mitra).
  Distributed Computing 29(2):77-88, 2016.
  Earlier version appears in ICALP '11.
• Wireless Capacity with Oblivious Power in General Metrics (with Pradipta Mitra).
  In SODA '11
• Wireless Communication is in APX (with Roger Wattenhofer).
  ICALP, July 2009 Retraction
• Capacity of Arbitrary Wireless Networks (with Olga Goussevskaia, Roger Wattenhofer, and Emo Welzl).
  INFOCOM, April 2009 Note on precedence and credit.

Modeling Aspects and Evaluations

• Wireless Link Capacity under Shadowing and Fading (with Tigran Tonoyan). June 2017.
In MobiHoc 2017.
• Invited paper: Models for wireless algorithms.
  WiOpt, May 2016.
• Wireless Scheduling Algorithms in Complex Environments (with Helga Gudmundsdottir, Eyjo Asgeirsson, Marijke Bodlaender, Joe Foley and Ymir Vigfusson)
  MSWiM'14
• Beyond Geometry : Towards Fully Realistic Wireless Models (with Marijke Bodlaender)
  PODC'14
• Invited paper: Modeling Reality Algorithmically: The Case of Wireless Communication.
  ALGOSENSORS, July 2013.

Distributed Algorithms

• Leveraging multiple channels in ad hoc networks
  Distributed Computing (with Yuexuan Wang and Dongxiao Yu), to appear. (earlier version)
• Data Dissemination in Unified Dynamic Wireless Networks (with Tigran Tonoyan, Yuexuan Wang, Dongxiao Yu)
  IPDPS, May 2017. (Full version)
• Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks
  PODC '16 (with Tigran Tonoyan, Yuexuan Wang, Dongxiao Yu)
• Leveraging Multiple Channels in Ad Hoc Networks
  PODC '15 (with Yuexuan Wang, Dongxiao Yu)
• A Local Broadcast Layer for the SINR Network Model (with
  PODC '15 (with Stephan Holzer, Nancy Lynch)
  Full version on arXiv
• Connectivity and aggregation in multihop wireless networks (with Marijke Bodlaender and Pradipta Mitra)
  PODC'13
• Towards Tight Bounds for Local Broadcasting (with Pradipta Mitra)
  FOMC'12
• Distributed Connectivity of Wireless Networks (with Pradipta Mitra)
  PODC'12
• Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model (with Pradipta Mitra).
  Distributed Computing 29(2):77-88, 2016.
  Earlier version appears in ICALP '11.

Connectivity and Aggregation

• Wireless Aggregation at Nearly Constant Rate (with Tigran Tonoyan), Dec 2017. (Poster at MobiHoc 2017.
• The Power of Non-Uniform Wireless Power (with Stephan Holzer, Pradipta Mitra and Roger Wattenhofer)
  SIAM Journal of Computing, 46(3):1062--1098, June 2017
• Connectivity and aggregation in multihop wireless networks (with Marijke Bodlaender and Pradipta Mitra)
  PODC'13
• The Power of Non-Uniform Wireless Power (with Stephan Holzer, Pradipta Mitra and Roger Wattenhofer)
  SODA'13, full version
• Distributed Connectivity of Wireless Networks (with Pradipta Mitra)
  PODC'12
• Wireless Connectivity and Capacity
  SODA '12 (with Pradipta Mitra).

Stochastic Packet Scheduling and Throughput

• Maximum MIMO Flow in wireless networks under the SINR model (with Eyjo Asgeirsson and Pradipta Mitra)
  WiOPT'14
• Wireless Network Stability in the SINR Model (with Eyjo Asgeirsson and Pradipta Mitra)
  SIROCCO'12
• A Fully Distributed Algorithm for Throughput Performance in Wireless Networks (with Eyjo Asgeirsson and Pradipta Mitra)
  CISS'12

Older papers on wireless (or wireless-motivated) problems in graph-based models

• Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
  Theoretical Computer Science, 2008 (with Takeshi Tokuyama). Earlier version appears in ALGOSENSORS '06
• On Spectrum Sharing Games
  PODC 2004 (with Joseph Y. Halpern, Li (Erran) Li, Vahab S. Mirrokni). Full version appears in Distributed Computing
• Approximating the (h,k)-labelling problem.
  Int. J. Mobile Mobile Network Design and Innovation 1(2):113--117, 2006.
Most recent papers are on arXiv.

---

Last revised 6 Dec 2016, Magnus M Halldorsson