Metric embedding via shortest path decompositions

DOI10.1145/3188745.3188808zbMath1427.68322arXiv1708.04073OpenAlexW2963298223MaRDI QIDQ5230353

Anupam Gupta, Ittai Abraham, Arnold Filtser, Ofer Neiman

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

normed spacespathwidthmetric embeddingsshortest path decompositiontreewidt

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Metric embeddings as related to computational problems and algorithms (68R12)

Related Items (4)

Lossless Prioritized Embeddings ⋮ Corrigendum: Metric Embedding via Shortest Path Decompositions ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ Covering Metric Spaces by Few Trees

This page was built for publication: Metric embedding via shortest path decompositions