Title

A Distributed Algorithm For Ear Decomposition

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.

Publication Date

1-1-1993

Publication Title

Proceedings - ICCI 1993: 5th International Conference on Computing and Information

Number of Pages

180-184

Document Type

Article; Proceedings Paper

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ICCI.1993.315382

Socpus ID

85064497764 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85064497764

This document is currently not available here.

Share

COinS