%0 Conference Paper
%B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
%D 1993
%T A distributed algorithm for ear decomposition
%A Hannenhalli, Sridhar
%A Perumalla,K.
%A Chandrasekharan,N.
%A Sridhar,R.
%K Asynchronous communication
%K asynchronous communication network
%K Automata
%K Communication networks
%K computational complexity
%K Computer networks
%K Computer science
%K decomposition graph
%K distributed algorithm
%K distributed algorithms
%K Distributed computing
%K Ear
%K ear decomposition
%K graph theory
%K message-optimal
%K network decomposition
%K sorting
%K Testing
%K time-optimal
%X 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
%B , Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
%I IEEE
%P 180 - 184
%8 1993/05/27/29
%@ 0-8186-4212-2
%G eng
%R 10.1109/ICCI.1993.315382