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 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-05529