✦ LIBER ✦
An algorithm for construction of a k-connected graph with minimum number of edges and quasiminimal diameter
✍ Scribed by Ulrich Schumacher
- Publisher
- John Wiley and Sons
- Year
- 1984
- Tongue
- English
- Weight
- 470 KB
- Volume
- 14
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Two fundamental considerations in the design of a communication network are reliability and maximum transmission delay. In this paper we give an algorithm for construction of an undirected graph with n vertices in which there are k node-disjoint paths between any two nodes. The generated graphs will have a minimum number of edges and a diameter which is twice as large as the theoretical minimum. The algorithm is useful for the construction of large networks because it has a time complexity of o(n2).