13. Sparse Partitions
David Peleg · Society for Industrial and Applied Mathematics eBooks · 2000
This chapter presents some algorithms for coarsening a given partition S of a given unweighted graph G. While the general picture emerging from the results presented next is similar to that of the previous chapter concerning covers, it turns out that for some of the sparsity measures we use, the problem is somewhat harder and we do not always get optimal bounds on the radius-sparsity trade-off.