2017/06/25 by Arnold Filtser, Filtser, Arnold · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1706.08115
openalex publication_date 2017/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Steiner point removal (SPR) problem, we are given a weighted graph G=(V,E) and a set of terminals K⊂ V of size k. The objective is to find a minor M of G with only the terminals as its vertex set, such that the distance between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer and Nguyen [KKN15] used a ball-growing algorithm with exponential distributions to show that the distortion is at most O(log5 k). Cheung [Che17] improved the analysis of the same algorithm, bounding the distortion by O(log2 k). We improve the analysis of this ball-growing algorithm even further, bounding the distortion by O(log k).