Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph

1964/06/01 by S. L. Hakimi · 2,402 citations
Engineering · Mathematics · #Advanced Research in Systems and Signal Processing #Center (category theory) #Combinatorics #Computer science #Engineering #Geometry #Graph #Intersection (aeronautics) #Mathematics #Median #Transport engineering #Vertex (graph theory)

paper · doi:10.1287/opre.12.3.450

published in Operations Research 12(3), 450-459 (Institute for Operations Research and the Management Sciences)

openalex publication_date 1964/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

The concepts of the “center” and the “median vertex” of a graph are generalized to the “absolute center” and the “absolute median” of a weighted graph (a graph with weights attached to its vertices as well as to its branches). These results are used to find the optimum location of a “switching center” in a communication network and to locate the best place to build a “police station” in a highway system. It is shown that the optimum location of a switching center is always at a vertex of the communication network while the best location for the police station is not necessarily at an intersection. Procedures for finding these locations are given.

Cited by

• The Location of Emergency Service Facilities
• Programming Models for Facility Dispersion: The p‐Dispersion and Maxisum Dispersion Problems
• Theoretical and Computational Links between the p‐Median, Location Set‐covering, and the Maximal Covering Location Problem
• Structure and temporal evolution of transportation literature
• Optimization approaches to identify cyclists’ route choice criteria
• A Foundational Perspective for Partitional Clustering on Networks
• Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems
• Ordered p-median problems with neighborhoods
• Capacitated Bounded Cardinality Hub Routing Problem: Model and Solution Algorithm
• Stochastic Emergency Response Units (ERUs) Allocation Considering\n Secondary Incident Occurrences
• Centrality in social networks conceptual clarification
• Optimizing Administrative Divisions: A Vertex k-Center Approach for Edge-Weighted Road Graphs
• Maximal Covering Location Problem: A Set Coverage Approach Using Dynamic Programming
• Network Centrality and Market Prices: An Empirical Note
• Fast approximation algorithms for the 1-median problem on real-world large graphs
• An efficient branch-and-cut approach for the sequential competitive facility location problem under partially binary rule
• Investigating State-of-the-Art Planning Strategies for Electric Vehicle Charging Infrastructures in Coupled Transport and Power Networks: A Comprehensive Review
• Algorithm for Two-Phase Facility Planning via Balanced Clustering and Integer Programming
• Target Location Problem for Multi-commodity Flow
• Equity Maximizing Facility Location Schemes
• Twenty-Five Years of Hub Location Research
• One-shot Robust Federated Learning of Independent Component Analysis
• A Flexible Reformulation of the Refueling Station Location Problem
• The p-Center Problem in Tree Networks Revisited
• A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution
• Coordinating Drop-Off Locations and Pickup Routes: A Budget-Constrained Routing Perspective
• Straightness of rectilinear vs. radio-concentric networks: modeling simulation and comparison
• Sustainable supply chain network design: An optimization-oriented review
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Four-point Fermat location problems revisited. New proofs and extensions of old results
• An Exact Algorithm for Large-scale Non-convex Quadratic Facility Location
• Audiovisual speaker diarization of TV series
• Design Approach for Additive Manufacturing in Spare Part Supply Chains
• Efficient Algorithms for the Weighted 2-Center Problem in a Cactus Graph
• Selecting the optimal healthcare centers with a modified P-median model: a visual analytic perspective. [europepmc]
• Robust optimization model and algorithm for railway freight center location problem in uncertain environment. [europepmc]
• Planning the City Logistics Terminal Location by Applying the Green p-Median Model and Type-2 Neurofuzzy Network. [europepmc]
• Analysis of Location Selection of Public Service Facilities Based on Urban Land Accessibility. [europepmc]
• Addressing the Location Problem of a Perishables Redistribution Center in the Middle of Europe. [europepmc]
• Reducing exposure to COVID-19 by improving access to fever clinics: an empirical research of the Shenzhen area of China. [europepmc]
• The Connected P -Median Problem on Cactus Graphs. [europepmc]
• Enhancing strategic defensive positioning and performance in the outfield. [europepmc]
• Optimization of Urban Shelter Locations Using Bi-Level Multi-Objective Location-Allocation Model. [europepmc]
• Optimization of Multi-Objective Mobile Emergency Material Allocation for Sudden Disasters. [europepmc]
• Accessibility of HIV Services in Philadelphia: Location-Allocation Analysis. [europepmc]
• Transit facility allocation: Hybrid quantum-classical optimization. [europepmc]
• Developing an agent-based model to minimize spreading of malicious information in dynamic social networks. [europepmc]
• Electric vehicle charging stations: Model, algorithm, simulation, location, and capacity planning. [europepmc]
• Supporting Fair and Efficient Emergency Medical Services in a Large Heterogeneous Region. [europepmc]
• Building non-motorized accessible communities for heterogeneous demand: A facility location and network design problem. [europepmc]
• K -Volume Clustering Algorithms for scRNA-Seq Data Analysis. [europepmc]
• A 5G Hubs Location Hierarchized Problem that Balances the Connection of the Users. [europepmc]

Related

• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• Optimal k-centers of a graph: a control-theoretic approach
• Finding the Center and Centroid of a Graph with Multiple Sources
• Optimizing Budget Allocation in Graphs
• On λ-Cent-Dians and Generalized-Center for Network Design: Definitions and Properties