A heuristic for the p-center problem in graphs
type: Item
instance of: scholarly article
title: A heuristic for the p-center problem in graphs
zbMATH Open document ID: 0637.05020
DOI: 10.1016/0166-218X(87)90029-1
author: Ján Plesník
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: The author gives an algorithm of \(O(n^ 2\log n)\) running time with a worst-case error ratio of 2 for the p-centerproblem in a connected graph of n nodes and m edges with edge lengths and vertex weights. A slight modification of the algorithm provides a ratio 2 also for the absolute p- center problem with running time \(O(mn^ 2\log n)\). Both heuristics are best possible.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4037889
zbMATH Keywords: center location
zbMATH Keywords: polynomial heuristics
zbMATH Keywords: algorithm
zbMATH Keywords: p-centerproblem
MaRDI profile type: Publication
cites work: Q4083324
cites work: The p-Centre Problem-Heuristic and Optimal Algorithms
cites work: A simple heuristic for the p-centre problem
cites work: Optimal packing and covering in the plane are NP-complete
cites work: Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
cites work: Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
cites work: A Best Possible Heuristic for the k-Center Problem
cites work: Easy and hard bottleneck location problems
cites work: Efficient Algorithms for Shortest Paths in Sparse Networks
cites work: An Algorithmic Approach to Network Location Problems. I: Thep-Centers
cites work: On the Complexity of Some Common Geometric Location Problems
cites work: The Centers and Medians of a Graph
cites work: On the computational complexity of centers locating in a graph
cites work: State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
cites work: State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
cites work: Q3220049
full work available at URL: 0166-218x(87)90029-1
OpenAlex ID: W2026564263
description: scientific article; zbMATH DE number 4037889