TY - Generic T1 - A distributed algorithm for ear decomposition T2 - Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93 Y1 - 1993 A1 - Sridhar Hannenhalli A1 - Perumalla, K. A1 - Chandrasekharan, N. A1 - Sridhar, R. KW - Asynchronous communication KW - asynchronous communication network KW - Automata KW - Communication networks KW - computational complexity KW - Computer networks KW - Computer science KW - decomposition graph KW - distributed algorithm KW - distributed algorithms KW - Distributed computing KW - Ear KW - ear decomposition KW - graph theory KW - message-optimal KW - network decomposition KW - sorting KW - Testing KW - time-optimal AB - 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 JA - Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93 PB - IEEE SN - 0-8186-4212-2 ER -