Back to Search
Start Over
OPTIMUM DISTRIBUTION OF SWITCHING CENTERS IN A COMMUNICATION NETWORK AND SOME RELATED GRAPH THEORETIC PROBLEMS.
- Source :
- Operations Research; May/Jun65, Vol. 13 Issue 3, p462, 14p
- Publication Year :
- 1965
-
Abstract
- 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]
Details
- Language :
- English
- ISSN :
- 0030364X
- Volume :
- 13
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 7042378
- Full Text :
- https://doi.org/10.1287/opre.13.3.462