Sparse Partitions (Extended Abstract
Baruch Awerbuch, David Peleg · 1990
1 ) Baruch Awerbuch David Peleg y Abstract: This abstract presents a collection of clustering and decomposition techniques enabling the construction of sparse and locality preserving representations for arbitrary networks. These new clustering techniques have already found several powerful applications in the area of distributed network algorithms. Two of these applications are described in this abstract, namely, routing with polynomial communication-space tradeoff and online tracking of mobile users. 1 Introduction 1.1 Motivation As networks grow larger, various control and management functions become increasingly more complex and expensive. Traditional protocols, based on a global approach, require all sites to participate in their activities, and to maintain considerable amounts of global information (e.g. topological data, status tables etc). This becomes problematic due to space considerations, the complexity of maintaining and updating this global information and the incre...