Title :
A distributed algorithm for ear decomposition
Author :
Hannenhalli, S. ; Perumalla, K. ; Chandrasekharan, N. ; Sridhar, R.
Author_Institution :
Dept. of Comput. Sci., Central Florida Univ., Orlando, FL, USA
Abstract :
A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition
Keywords :
computational complexity; computer networks; distributed algorithms; graph theory; asynchronous communication network; decomposition graph; distributed algorithm; ear decomposition; message-optimal; network decomposition; time-optimal; Asynchronous communication; Automata; Communication networks; Computer networks; Computer science; Distributed algorithms; Distributed computing; Ear; Sorting; Testing;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315382
