A heuristic for the p-center problem in graphs

DOI10.1016/0166-218X(87)90029-1zbMath0637.05020OpenAlexW2026564263MaRDI QIDQ1098862

Ján Plesník

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(87)90029-1

zbMATH Keywords

algorithmcenter locationp-centerproblempolynomial heuristics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (33)

The \(p\)-neighbor \(k\)-center problem ⋮ Asymmetric \(k\)-center with minimum coverage ⋮ Generalized eccentricity, radius, and diameter in graphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ On some variants of Euclidean \(k\)-supplier ⋮ The multi-service center problem ⋮ Approximating the asymmetric \(p\)-center problem in parameterized complete digraphs ⋮ Approximability results for the $p$-centdian and the converse centdian problems ⋮ Min-Max-Min Optimization with Smooth and Strongly Convex Objectives ⋮ Approximability results for the converse connectedp-centre problem^† ⋮ Some variations on constrained minimum enclosing circle problem ⋮ On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph ⋮ A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem ⋮ Lexicographic local search and the \(p\)-center problem. ⋮ VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION ⋮ Graph clustering ⋮ The fault-tolerant capacitated \(K\)-center problem ⋮ An optimal algorithm for the weighted backup 2-center problem on a tree ⋮ The minimum weight \(t\)-composition of an integer ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ An approximation algorithm for the edge-dilation \(k\)-center problem. ⋮ \(k\)-center problems with minimum coverage ⋮ Approximation algorithm for the kinetic robust \(k\)-center problem ⋮ Facility location with dynamic distance functions ⋮ Asymmetry in \(k\)-center variants ⋮ Solving thep-Center problem with Tabu Search and Variable Neighborhood Search ⋮ Mathematical Models and Search Algorithms for the Capacitated p-Center Problem ⋮ The weighted \(k\)-center problem in trees for fixed \(k\) ⋮ Fault tolerant \(K\)-center problems ⋮ A new assignment rule to improve seed points algorithms for the continuous \(k\)-center problem ⋮ On interval and circular-arc covering problems ⋮ One-way and round-trip center location problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• A simple heuristic for the p-centre problem
• Easy and hard bottleneck location problems
• Optimal packing and covering in the plane are NP-complete
• On the Complexity of Some Common Geometric Location Problems
• The p-Centre Problem-Heuristic and Optimal Algorithms
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• A Best Possible Heuristic for the k-Center Problem
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• On the computational complexity of centers locating in a graph
• Efficient Algorithms for Shortest Paths in Sparse Networks
• The Centers and Medians of a Graph
• Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph

This page was built for publication: A heuristic for the p-center problem in graphs