@conference {14576,
title = {A distributed algorithm for ear decomposition},
booktitle = {, Fifth International Conference on Computing and Information, 1993. Proceedings ICCI {\textquoteright}93},
year = {1993},
month = {1993/05/27/29},
pages = {180 - 184},
publisher = {IEEE},
organization = {IEEE},
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 = {Asynchronous communication, asynchronous communication network, Automata, Communication networks, computational complexity, Computer networks, Computer science, decomposition graph, distributed algorithm, distributed algorithms, Distributed computing, Ear, ear decomposition, graph theory, message-optimal, network decomposition, sorting, Testing, time-optimal},
isbn = {0-8186-4212-2},
doi = {10.1109/ICCI.1993.315382},
author = {Hannenhalli, Sridhar and Perumalla,K. and Chandrasekharan,N. and Sridhar,R.}
}