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

DOI10.1016/j.jcss.2019.04.006zbMath1423.68326arXiv1609.08801OpenAlexW2943137904WikidataQ127887906 ScholiaQ127887906MaRDI QIDQ2316932

Ofer Neiman, Arnold Filtser, Yair Bartal

Publication date: 7 August 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1609.08801

zbMATH Keywords

metric embeddingaverage distortionlight spannerprioritized distortionscaling distortion

Mathematics Subject Classification ID

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

Related Items (4)

Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Constructing light spanners deterministically in near-linear time

Cites Work

• Unnamed Item
• Unnamed Item
• Volume in general metric spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Terminal embeddings
• Approximate Distance Oracles with Improved Bounds
• Prioritized Metric Structures and Embedding
• Triangulation and embedding using small sets of beacons
• Lower-Stretch Spanning Trees
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Near-Optimal Light Spanners
• On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• Constructing Light Spanners Deterministically in Near-Linear Time
• Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
• The Greedy Spanner is Existentially Optimal
• Using petal-decompositions to build a low stretch spanning tree
• Spanners with Slack
• Algorithms – ESA 2004
• Light Spanners
• Steiner Minimal Trees
• Advances in metric embedding theory
• A tight bound on approximating arbitrary metrics by tree metrics

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