Approximability results for the converse connectedp-centre problem†
DOI10.1080/00207160.2015.1077235zbMath1404.68206OpenAlexW1577861748MaRDI QIDQ2958261
Publication date: 1 February 2017
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207160.2015.1077235
computational complexitycombinatorial optimizationapproximation algorithmNP-hardness\(p\)-centre problemconverse connected \(p\)-centre problemfacility location with load balancing
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The connected \(p\)-center problem on block graphs with forbidden vertices
- Complexity and approximation of the connected set-cover problem
- A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
- Clustering to minimize the maximum intercluster distance
- A heuristic for the p-center problem in graphs
- Easy and hard bottleneck location problems
- Optimization, approximation, and complexity classes
- Generalized \(p\)-center problems: Complexity results and approximation algorithms
- Approximation algorithms for connected dominating sets
- Location analysis: a synthesis and survey
- A bibliography for some fundamental problem categories in discrete location science
- What you should know about location modeling
- State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
- Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Towards a theory of domination in graphs
- Bicriteria Network Design Problems
- How to Allocate Network Centers
- Routing to Multiple Destinations in Computer Networks
- Genetic algorithm to solve the p-centre and p-radius problem on a network
- Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
This page was built for publication: Approximability results for the converse connectedp-centre problem†
