摘要：A partition ð'« of a weighted graph G is (Ïf,Ï",Î")-sparse if every cluster has diameter at most Î", and every ball of radius Î"/Ïf intersects at most Ï" clusters. Similarly, ð'« is (Ïf,Ï",Î")-scattering if instead for balls we require that every shortest path of length at most Î"/Ïf intersects at most Ï" clusters. Given a graph G that admits a (Ïf,Ï",Î")-sparse partition for all Î" > 0, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch O(Ï"Ïf²log_Ï" n). Given a graph G that admits a (Ïf,Ï",Î")-scattering partition for all Î" > 0, we construct a solution for the Steiner Point Removal problem with stretch O(Ï"³Ïf³). We then construct sparse and scattering partitions for various different graph families, receiving many new results for the Universal Steiner Tree and Steiner Point Removal problems.
