Approximability results for the converse connected p-centre problem

DOI10.1080/00207160.2015.1077235MaRDI QIDQ2958261zbMATH OpenOpenAlexFDO

Authors Yen Hung Chen

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

zbMATH Keywords

computational complexitycombinatorial optimizationapproximation algorithmNP-hardness\(p\)-centre problemconverse connected \(p\)-centre problemfacility location with load balancing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• scientific article; zbMATH DE number 5205606
• The connected p-center problem on block graphs with forbidden vertices
• The connected \(p\)-center problem on cactus graphs
• A simple greedy approximation algorithm for the minimum connected k-center problem
• The connected \(p\)-center problem on cactus graphs

Cites work

• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A bibliography for some fundamental problem categories in discrete location science
• A heuristic for the p-center problem in graphs
• A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
• Approximation algorithms for connected dominating sets
• Clustering to minimize the maximum intercluster distance
• Complexity and approximation of the connected set-cover problem
• Easy and hard bottleneck location problems
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Generalized p-center problems: Complexity results and approximation algorithms
• Genetic algorithm to solve the p-centre and p-radius problem on a network
• How to Allocate Network Centers
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• Location analysis: a synthesis and survey
• Optimization, approximation, and complexity classes
• Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
• Routing to Multiple Destinations in Computer Networks
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• The connected p-center problem on block graphs with forbidden vertices
• Towards a theory of domination in graphs
• What you should know about location modeling

Cited in

(6)

• Approximating the Restricted 1-Center in Graphs
• A simple greedy approximation algorithm for the minimum connected k-center problem
• Approximability results for the $p$-centdian and the converse centdian problems
• Generalized p-center problems: Complexity results and approximation algorithms
• Un nuevo resultado sobre la complejidad del problema delP-centro
• scientific article; zbMATH DE number 5205606 (Why is no real title available?)

This page was built for publication: Approximability results for the converse connected \(p\)-centre problem

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