On the hardness of range assignment problems

DOI10.1002/NET.20227MaRDI QIDQ3548718zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(14)

• Submodular formulations for range assignment problems
• On the Hardness of Range Assignment Problems
• Structural Information and Communication Complexity
• A geometric characterisation of the quadratic min-power centre
• Probabilistic properties of highly connected random geometric graphs
• 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
• 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)