Sparse partitions
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 503-513
- https://doi.org/10.1109/fscs.1990.89571
Abstract
1)Baruch AwerbuchDavid Pelegy This abstract presents a collection of clusteringand decomposition techniques enabling the constructionof sparse and locality preserving representations forarbitrary networks. These new clustering techniques havealready found several powerful applications in the area ofdistributed network algorithms. Two of these applicationsare described in this abstract, namely, routing with polynomialcommunication-space tradeoff and online trackingof...Keywords
This publication has 15 references indexed in Scilit:
- Network synchronization with polylogarithmic overheadPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Generating sparse spanners for weighted graphsLecture Notes in Computer Science, 1990
- Network decomposition and locality in distributed computationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Distributed match-makingAlgorithmica, 1988
- Designing networks with compact routing tablesAlgorithmica, 1988
- Establishing virtual circuits in large computer networksComputer Networks and ISDN Systems, 1986
- Complexity of network synchronizationJournal of the ACM, 1985
- Towards a universal directory servicePublished by Association for Computing Machinery (ACM) ,1985
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Hierarchical routing for large networks Performance evaluation and optimizationComputer Networks (1976), 1977