A new characterization of tree medians with applications to distributed sorting

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 [n/2] disjoint pairs (excluding m when n is odd), such that all the paths connecting the two vertices in any of the pairs pass thro...

Full description

Saved in:
Bibliographic Details
Published in:Networks 1994-01, Vol.24 (1), p.23-29
Main Authors: Gerstel, O., Zaks, S.
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Teletraffic
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 [n/2] 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 the sum of the distances between these pairs of vertices 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. We show that, given a network of a tree topology, choosing a median and then routing 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. © 1994 by John Wiley & Sons, Inc.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.3230240104