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

S. L. Hakimi
Additional contact information
S. L. Hakimi: The Technological Institute, Northwestern University, Evanston, Illinois

Operations Research, 1965, vol. 13, issue 3, 462-475

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.

Date: 1965
References: Add references at CitEc
Citations: View citations in EconPapers (149)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.13.3.462 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:13:y:1965:i:3:p:462-475

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().