Premium
An algorithm for construction of a k ‐connected graph with minimum number of edges and quasiminimal diameter
Author(s) -
Schumacher Ulrich
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140106
Subject(s) - disjoint sets , combinatorics , undirected graph , algorithm , node (physics) , graph , time complexity , strongly connected component , connectivity , mathematics , computer science , minimum cut , discrete mathematics , structural engineering , engineering
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(n 2 ) .