Distributed algorithms for network recognition problems
K.V.S. Ramarao · IEEE Transactions on Computers · 1989
The problem of recognizing whether a given network is a tree, ring, star, complete graph, or bipartite graph is considered. Unified algorithms to recognize if the network is any one of the above are presented in each of three classes of algorithms-with centralized, decentralized, and noncentralized initiations. It is shown that the communication and time complexities of the centralized algorithm are linear in e and d, respectively, while those for decentralized algorithm are O(e+n log n) and O(n), respectively (e is the number of edges, n is the number of processors, and d is the diameter of the graph). The complexities for noncentralized algorithms are, respectively O(e+n log k), where k is the level number, and O(n).>