Technical Report CS0693

TR#:CS0693
Class:CS
Title: A NEW CHARACTERIZATION OF TREE MEDIANS WITH APPLICATIONS TO DISTRIBUTED ALGORITHMS
Authors: O. Gerstel and S. Zaks
PDF - RevisedCS0693.revised.pdf
Abstract: A new characterization of tree medians is presented: we show that a vertex $m$ is a median of a tree $T$ with $n$ vertices iff there exists a partition of the vertex set into $\lfloor n/2 \rfloor$ disjoint pairs (excluding $m$ when $n$ is odd), such that all the paths connecting the two vertices in any of the pairs pass through $m$. We show that in this case this sum is the largest possible among all such partitions, and we use this fact to discuss lower bounds on the message complexity of the distributed sorting problem. This lower bound implies that, given a network of a tree topology, choosing a median and then route all the information through it is the best possible strategy, in terms of worst-case number of messages sent during any execution of any distributed sorting algorithm. We also discuss the implications for networks of a general topology and for the distributed ranking problem.
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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0693), 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 1991
To the main CS technical reports page

Computer science department, Technion
admin