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

embeddingsfour-points conditionmetric spacestree metrics

Mathematics Subject Classification ID

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

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)

• An optimal algorithm to reconstruct trees from additive distance data
• 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
• Distributed approaches to triangulation and embedding
• Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics
• Recognition of Tree Metrics
• Recovering Trees with Convex Clustering
• Distributed Relationship Schemes for Trees
• A tight bound on approximating arbitrary metrics by tree metrics
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximating snowflake metrics by trees

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)