A distributed algorithm for ear decomposition

TitleA distributed algorithm for ear decomposition
Publication TypeConference Proceedings
Year of Conference1993
AuthorsHannenhalli S, Perumalla K., Chandrasekharan N., Sridhar R.
Conference Name Fifth International Conference on Computing and Information, 1993. Proceedings ICCI '93
Date Published1993
ISBN Number0-8186-4212-2
KeywordsAsynchronous 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

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