Steiner point removal with distortion O( k)

MaRDI QIDQ4607978zbMATH OpenFDO

Authors Arnold Filtser

Publication date 15 March 2018

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

Mathematics Subject Classification ID

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

Recommendations

• Steiner point removal -- distant terminals don't (really) bother
• 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

(11)

• A Tight Lower Bound for the Steiner Point Removal Problem on Trees
• Steiner point removal -- distant terminals don't (really) bother
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Aggregation over metric spaces: proposing and voting in elections, budgeting, and legislation
• Refined vertex sparsifiers of planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• Cutting corners cheaply, or how to remove Steiner points
• Cutting Corners Cheaply, or How to Remove Steiner Points
• Scattering and sparse partitions, and their applications
• O(1) Steiner point removal in series-parallel graphs
• Scattering and sparse partitions, and their applications

This page was built for publication: Steiner point removal with distortion \(O(\log k)\)

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