OPTIMUM DISTRIBUTION OF SWITCHING CENTERS IN A COMMUNICATION NETWORK AND SOME RELATED GRAPH THEORETIC PROBLEMS.

The concept of a median in a weighted graph is generalized to a multi- median. 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 distanced? 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 pos- sible subgraphs of G with given degrees. [ABSTRACT FROM AUTHOR]