Technical Report CS0431

Title: Stepwise Construction of an Efficient Distributed Traversing Algorithm for General Strongly Connected Directed Graphs (or: Traversing One Way Streets
Authors: Shay Kutten
Abstract: We study the problem of distributively traversing directed networks, and constructing directed spanning trees. New tight lower ami upper bounds on the message complexity are given. Using the algorithm we present better solutions for ptoblems in directed graphs can be achieved. Among others, a leader election algorithm, which is better then existing ones for a very large family of graphs, is achieved. Also, the message complexity of performing a broadcast, either with or without acknowledgements, is reduced. Such an algorithm is also needed in radio networks in order to coordinate transmissions. The traversing algorithm is constructed step by step, starting from a very simple algorithm to traverse directed rings. The algorithm is developed by going on changing the assumptions on the graph, and changing the algorithm as a result.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1986
To the main CS technical reports page

Computer science department, Technion