Diameters of communication networks. (English) Zbl 0595.94025
Mathematics of information processing, AMS Short Course, Louisville/Ky. 1984, Proc. Symp. Appl. Math. 34, 1-18 (1986).
Summary: [For the entire collection see Zbl 0578.00002.]
When graphs are used to model the linkage structure of communication networks, the diameter of the graph corresponds to the maximum number of links over which a message between two nodes must travel. In cases where the number of links in a path is roughly proportional to the time delay or signal degradation encountered by messages sent along the path, the diameter is then involved in the complexity analysis for the performance of the networks. A variety of interrelated diameter problems will be discussed here, including: determining extremal graphs of bounded degrees and small diameters, finding orientations for undirected or mixed graphs to minimize diameters; investigating diameter bounds for networks with possible node and link failures, and algorithmic aspects for determining the diameter of graphs.
When graphs are used to model the linkage structure of communication networks, the diameter of the graph corresponds to the maximum number of links over which a message between two nodes must travel. In cases where the number of links in a path is roughly proportional to the time delay or signal degradation encountered by messages sent along the path, the diameter is then involved in the complexity analysis for the performance of the networks. A variety of interrelated diameter problems will be discussed here, including: determining extremal graphs of bounded degrees and small diameters, finding orientations for undirected or mixed graphs to minimize diameters; investigating diameter bounds for networks with possible node and link failures, and algorithmic aspects for determining the diameter of graphs.
MSC:
| 94C15 | Applications of graph theory to circuits and networks |
