Reconstructing approximate tree metrics

DOI10.1145/1281100.1281110MaRDI QIDQ5401392zbMATH OpenOpenAlexFDO

Authors Ittai Abraham, M. Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Venugopalan Ramasubramanian, Kunal Talwar

Publication date 13 March 2014

Published in Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1281100.1281110

zbMATH Keywords

metric spacesembeddingstree metricsfour-points condition

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Distance in graphs (05C12) Internet topics (68M11)

Recommendations

• A tight bound on approximating arbitrary metrics by tree metrics
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximation algorithms for embedding general metrics into trees
• scientific article; zbMATH DE number 1775401
• scientific article; zbMATH DE number 1775400

Cited in

(12)

• Distributed approaches to triangulation and embedding
• A tight bound on approximating arbitrary metrics by tree metrics
• An optimal algorithm to reconstruct trees from additive distance data
• Approximating snowflake metrics by trees
• A tight bound on approximating arbitrary metrics by tree metrics
• Gromov-Hausdorff approximation of filamentary structures using Reeb-type graphs
• How to use spanning trees to navigate in graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics
• Recovering Trees with Convex Clustering
• Distributed Relationship Schemes for Trees
• Recognition of Tree Metrics

This page was built for publication: Reconstructing approximate tree metrics

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