Steiner point removal -- distant terminals don't (really) bother

MaRDI QIDQ4607977zbMATH OpenFDO

Authors Yun Kuen Cheung

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1703.08790, http://dl.acm.org/citation.cfm?id=3175394

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Signed and weighted graphs (05C22) Graph minors (05C83)

Abstract: Given a weighted graph $G=(V,E,w)$ with a set of $k$ terminals $TsubsetV$, the Steiner Point Removal problem seeks for a minor of the graph with vertex set $T$, such that the distance between every pair of terminals is preserved within a small multiplicative distortion. Kamma, Krauthgamer and Nguyen (SODA 2014, SICOMP 2015) used a ball-growing algorithm to show that the distortion is at most $mathcalO(lo{g}^{5}k)$ for general graphs. In this paper, we improve the distortion bound to $mathcalO(lo{g}^{2}k)$. The improvement is achieved based on a known algorithm that constructs terminal-distance exact-preservation minor with $mathcalO(k^4)$ (which is independent of $|V|$) vertices, and also two tail bounds on the sum of independent exponential random variables, which allow us to show that it is unlikely for a non-terminal being contracted to a distant terminal.

Recommendations

• Steiner point removal with distortion \(O(\log k)\)
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Cutting corners cheaply, or how to remove Steiner points
• Cutting Corners Cheaply, or How to Remove Steiner Points
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees

Cited in

(9)

• Cutting corners cheaply, or how to remove Steiner points
• Improved guarantees for vertex sparsification in planar graphs
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Steiner point removal with distortion \(O(\log k)\)
• How Many Steiner Terminals Can You Connect in 20 Years?
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Refined vertex sparsifiers of planar graphs
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees

This page was built for publication: Steiner point removal -- distant terminals don't (really) bother

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607977)