Related Experiment Video
Updated: Jun 12, 2025

Using Phylogenetic Analysis to Investigate Eukaryotic Gene Origin
Published on: August 14, 2018
Accelerating Computation of Stable Merge Tree Edit Distances Using Parameterized Heuristics
Abstract:
In this paper, we present a novel heuristic algorithm for the stable but NP-complete deformation-based edit distance on merge trees. Our key contribution is the introduction of a user-controlled look-ahead parameter that allows to trade off accuracy and computational cost. We achieve a fixed parameter tractable running time that is polynomial in the size of the input but exponential in the look-ahead value. This extension unlocks the potential of the deformation-based edit distance in handling saddle swaps, while maintaining feasible computation times. Experimental results demonstrate the computational efficiency and effectiveness of this approach in handling specific perturbations.
Related Concept Videos
Distance Corrections
Heuristics
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
Wilcoxon Signed-Ranks Test for Matched Pairs
Evolutionary Relationships through Genome Comparisons
Phylogenetic Trees
Survival Tree
Building a Survival Tree
Constructing a...

