Minimizing the Maximum Interference is Hard

2008/02/15 by Kevin Buchin, Buchin, Kevin · 2 citations
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI) #Vehicular Ad Hoc Networks (VANETs)

paper · pdf · doi:10.48550/arxiv.0802.2134

openalex publication_date 2008/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges as disks. For this case we show that choosing transmission radii which minimize the maximum interference while maintaining a connected symmetric communication graph is NP-complete.

Cited by

• A Tight Bound on the Maximum Interference of Random Sensors in the Highway Model
• Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random\n Position

Related

• Interference Minimization in Asymmetric Sensor Networks
• Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random\n Position
• Minimizing interference in ad-hoc networks with bounded communication\n radius
• Minimizing Total Interference in Asymmetric Sensor Networks
• Improved Interference in Wireless Sensor Networks