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 -