A heuristic for the p-center problem in graphs (Q1098862)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A heuristic for the p-center problem in graphs |
scientific article; zbMATH DE number 4037889
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A heuristic for the p-center problem in graphs |
scientific article; zbMATH DE number 4037889 |
Statements
A heuristic for the p-center problem in graphs (English)
0 references
1987
0 references
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.
0 references
center location
0 references
polynomial heuristics
0 references
algorithm
0 references
p-centerproblem
0 references
0 references
0 references
0 references
