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

DOI10.1137/1.9781611974331.CH62MaRDI QIDQ4575641zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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)