An algorithm for construction of a  k ‐connected graph with minimum number of edges and quasiminimal diameter | Zendy

Schumacher Ulrich | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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 ) .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research