返回Google圖書搜尋

A New Characterization of Tree Medians with Applications of Distributed Algorithms

Ṭekhniyon, Makhon ṭekhnologi le-Yiśraʼel. Maḥlaḳah le-madaʻe ha-maḥshevO. GerstelShmuel Zaks

出版	Aarhus University, Computer Science Department, 1991
URL	http://books.google.com.hk/books?id=X0RuHAAACAAJ&hl=&source=gbs_api

註釋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 [greatest integer less than or equal to 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 this sum is the largest possible among all such partitions, and we this fact to discuss lower bounds on the message complexity of the distributed sorting problem.