FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees

DOI10.4230/LIPICS.ESA.2019.83MaRDI QIDQ5075834zbMATH OpenOpenAlexFDO

Authors Elena Farahbakhsh Touli, Yusu Wang

Publication date 11 May 2022

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

zbMATH Keywords

Gromov-Hausdorff distanceinterleaving distancemerge trees

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Metric spaces, metrizability (54E35)

Recommendations

• FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
• Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching
• Determining the Hausdorff distance between trees in polynomial time

Cites work

• A survey on tree edit distance and related problems
• A theoretical and computational framework for isometry invariant recognition of point cloud data
• Alignment of trees -- an alternative to tree edit
• Approximation algorithms for embedding general metrics into trees
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Categorified Reeb graphs
• Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
• Efficient Computation of Isometry‐Invariant Distances Between Surfaces
• Fitting Tree Metrics: Hierarchical Clustering and Phylogeny
• Measuring distance between Reeb graphs (extended abstract)
• Measuring the distance between merge trees
• Metric embeddings with outliers
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics
• Reeb graphs for shape analysis and applications
• Some MAX SNP-hard results concerning unordered labeled trees
• Some properties of Gromov-Hausdorff distances
• The Reeb graph edit distance is universal
• Topological quadrangulations of closed triangulated surfaces using the Reeb graph

Cited in

(7)

• The Reeb graph edit distance is universal
• Measuring the distance between merge trees
• Determining the Hausdorff distance between trees in polynomial time
• FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
• The ultrametric Gromov-Wasserstein distance
• Decorated merge trees for persistent topology
• Labeled interleaving distance for Reeb graphs

This page was built for publication: FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees

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