Accelerating Computation of Stable Merge Tree Edit Distances using Parameterized Heuristics

\authororcid Florian Wetzels0000-0002-5526-7138, \authororcid Heike Leitte0000-0002-7112-2190, and \authororcid Christoph Garth0000-0003-1669-8549 · 2025

Read Accelerating Computation of Stable Merge Tree Edit Distances using Parameterized Heuristics by \authororcid Florian Wetzels0000-0002-5526-7138, \authororcid Heike Leitte0000-0002-7112-2190, and \authororcid Christoph Garth0000-0003-1669-8549 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05529.txt.

Description

Florian Wetzels, Heike Leitte, and Christoph Garth present a faster way to measure how different two merge trees are. Merge trees summarize the shape of data, and the deformation-based edit distance between them is stable but NP-complete, so exact answers are slow to get. Their heuristic algorithm adds a look-ahead setting that the user controls, letting accuracy be traded against computing cost. The running time stays polynomial in the size of the input while growing exponentially only in that look-ahead value.

The extension makes the distance usable on cases involving saddle swaps, which earlier methods handled poorly. Experiments reported by the authors show that the approach stays efficient and effective on the specific disturbances they tested. The method opens the edit distance to larger problems where exact computation would take too long.

Catalog record

CREATOR\authororcid Florian Wetzels0000-0002-5526-7138, \authororcid Heike Leitte0000-0002-7112-2190, and \authororcid Christoph Garth0000-0003-1669-8549
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05529

Browse the full library · About the Tower of Babel