On notions of distortion and an almost minimum spanning tree with constant average distortion

DOI10.1137/1.9781611974331.CH62zbMATH Open1410.68276OpenAlexW2949625395MaRDI QIDQ4575641FDOQ4575641

Authors: Arnold Filtser, Ofer Neiman, Yair Bartal 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch62

Recommendations

• On notions of distortion and an almost minimum spanning tree with constant average distortion
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Viewing the rings of a tree: minimum distortion embeddings into trees
• scientific article; zbMATH DE number 437549

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Cited In (6)

• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Lossless prioritized embeddings
• Terminal embeddings
• Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• On notions of distortion and an almost minimum spanning tree with constant average distortion

This page was built for publication: On notions of distortion and an almost minimum spanning tree with constant average distortion

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