Title :
Distributed algorithms on edge connectivity problems
Author :
Yang, Shi-Nine ; Cheng, Ming-Shiuan
Author_Institution :
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Abstract :
Connectivity of a network dictates the routability and survivability of a network. The paper investigates the edge connectivity problems in distributed environments. For a given network or graph G, one can distributively find bridges in the network first then find the 2-edge connected components. Both algorithms proposed, bridge finding and 2-edge connected component identifying, require only O(m) message complexity, where m is the number of edge in G. The paper also shows an efficient distributed 2-edge cutset algorithm that has O(n2) message complexity, where n is the number of nodes in G
Keywords :
computational complexity; distributed algorithms; graph theory; 2-edge connected components; bridge finding; distributed 2-edge cutset algorithm; distributed algorithms; distributed environments; edge connectivity problems; graph; message complexity; routability; survivability; Bridge circuits; Circuit synthesis; Communication networks; Computer science; Councils; Distributed algorithms; Integrated circuit interconnections; Labeling; Multiprocessor interconnection networks; Telecommunication network reliability;
Conference_Titel :
Parallel and Distributed Processing, 1993. Proceedings of the Fifth IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-4222-X
DOI :
10.1109/SPDP.1993.395468
