Complexity of the repeaters allocating problem

DOI10.1016/S0020-0190(05)80004-3MaRDI QIDQ1183426zbMATH OpenOpenAlexFDO

Authors Nen-Fu Huang, Ching-Ho Huang

Publication date 28 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(05)80004-3

zbMATH Keywords

approximation algorithmNP-hardset covering problemstrong connectivitygeometric location problemrepeaters allocating problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the complexity of two circle connecting problems
• Algorithm Theory - SWAT 2004
• scientific article; zbMATH DE number 969990
• On the hardness of range assignment problems
• On the Hardness of Range Assignment Problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Approximation algorithms for combinatorial problems
• Depth-First Search and Linear Graph Algorithms
• On the Complexity of Some Common Geometric Location Problems
• On the complexity of two circle strongly connecting problems
• On the ratio of optimal integral and fractional covers

Cited in

(1)

• Radar placement along banks of river

This page was built for publication: Complexity of the repeaters allocating problem

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