On the hardness of range assignment problems

DOI10.1002/NET.20227zbMATH Open1157.68031OpenAlexW315629273MaRDI QIDQ3548718FDOQ3548718

Authors: Bernhard Fuchs 

Publication date: 17 December 2008

Published in: Networks (Search for Journal in Brave)

Full work available at URL: http://e-archive.informatik.uni-koeln.de/488/2/zaik2005-488.pdf

Recommendations

• On the Hardness of Range Assignment Problems
• On the minimum cost range assignment problem
• Assign ranges in general ad-hoc networks
• Algorithmic Applications in Management
• Structural Information and Communication Complexity

zbMATH Keywords

computational complexityapproximation algorithmswireless networkshardness of approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40)

Cites Work

• Optimization, approximation, and complexity classes
• Approximation algorithms for NP-complete problems on planar graphs
• Automata, Languages and Programming
• Inapproximability results for bounded variants of optimization problems.
• Some simplified NP-complete graph problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Power consumption in packet radio networks
• Minimum-cost coverage of point sets by disks
• Approximation and Online Algorithms
• The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings
• The minimum broadcast range assignment problem on linear multi-hop wireless networks.

Cited In (15)

• Submodular formulations for range assignment problems
• On the Hardness of Range Assignment Problems
• Structural Information and Communication Complexity
• Probabilistic properties of highly connected random geometric graphs
• A geometric characterisation of the quadratic min-power centre
• Approximation algorithms for minimum power \(k\) backbone node \(r\)-connected subgraph problem in wireless sensor networks
• On the difficulty of range searching.
• The Online Broadcast Range-Assignment Problem
• Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem
• The online broadcast range-assignment problem
• A greedy topology design to accelerate consensus in broadcast wireless sensor networks
• Complexity of the repeaters allocating problem
• Connecting a set of circles with minimum sum of radii
• The homogeneous broadcast problem in narrow and wide strips. I: Algorithms
• Construction of minimum power 3-connected subgraph with \(k\) backbone nodes in wireless sensor networks

This page was built for publication: On the hardness of range assignment problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3548718)