ComputingComputer ScienceMathematicsComputer NetworksData StructuresRepresentation TheoryGraph AlgorithmsGraph TheoryNetwork ModelingNetwork StructureNetwork TopologyClusteringClustering AlgorithmsGraph DecompositionsNetwork PartitioningNetwork Representation
A collection of clustering and decomposition techniques that make possible the construction of sparse and locality-preserving representations for arbitrary networks is presented. The representation method considered is based on breaking the network G(V,E) into connected regions, or clusters, thus obtaining a cover for the network, i.e. a collection of clusters that covers the entire set of vertices V. Several other graph-theoretic structures that are strongly related to covers are discussed. These include sparse spanners, tree covers of graphs and the concepts of regional matchings and diameter-based separators. All of these structures can be constructed by means of one of the clustering algorithms given, and each has proved a convenient representation for handling certain network applications.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
15
A Separator Theorem for Planar Graphs
Richard J. Lipton, Robert E. Tarjan · SIAM Journal on Applied Mathematics · 1979 · 1.4K citations
Complexity of network synchronization
Baruch Awerbuch · Journal of the ACM · 1985 · 691 citations · Full text
David Peleg, Alejandro A. Schäffer · Journal of Graph Theory · 1989 · 419 citations
An Optimal Synchronizer for the Hypercube
David Peleg, Jeffrey D. Ullman · SIAM Journal on Computing · 1989 · 347 citations