Introvert Clustering for Distributed Graph Algorithms
We introduce a graph decomposition primitive called introvert clustering, which strengthens standard low-diameter clustering by guaranteeing that every clustered vertex keeps at least a $\left(\frac12-\varepsilon\right)$-fraction of its relevant neighbors in its own cluster. Repeatedly applying this primitive yields a...
Yi-Jun Chang, Nima Dolatabadi
· 0 citations