Distance-Preserving Graph Contractions
Distance-Preserving Graph Contractions
Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large networks/graphs. In this paper we propose and study a new framework contracting edges of a graph (merging vertices into supervertices) with the goal of preserving pairwise distances as accurately as possible. Formally, given an …