Complexity of the repeaters allocating problem

DOI10.1016/S0020-0190(05)80004-3zbMath0748.68086OpenAlexW2014642266MaRDI QIDQ1183426

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)

Cites Work

• Unnamed Item
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• On the Complexity of Some Common Geometric Location Problems
• 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
• On the complexity of two circle strongly connecting problems
• Depth-First Search and Linear Graph Algorithms

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