Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems

TLDR

The median concept in weighted graphs is extended to a multimedian. The study seeks the optimal placement of p switching centers in a communication network and the minimal number of policemen needed in a highway network to keep all points within distance d. The authors generate all vertex‑coverings of a graph using a Boolean function over its vertices, then extend this approach to produce all matchings, factors, and degree‑constrained subgraphs. They prove that the optimal placement of p switching centers corresponds to a p‑median of the weighted graph.

Abstract

The concept of a median in a weighted graph is generalized to a multimedian. Then, it is shown that the optimum distribution of p switching centers in a communication network is at a p-median of the corresponding weighted graph. The following related problem in highway networks is also considered: What is a minimum number of policemen that can be distributed in a highway network so that no one is farther away from a policeman than a given distance d? This problem is attacked by generating all vertex-coverings (externally stable sets) of a graph by means of a Boolean function defined over the vertices of a graph. Then this idea is extended to Boolean functions that generate all matchings, all factors, and all possible subgraphs of G with given degrees.