RSPR version history

1.02

• Includes a cluster reduction step that greatly improves performance in many cases
• Provides an option to find the total rooted SPR distance between the first input tree and each of the remaining input trees
• Stand-alone version of the calculations used in "Subtree Prune-and-Regraft Supertrees."

1.01

• Optimized branching cases, improving the complexity to O(2.42^k n), where k is the rooted SPR distance and n is the number of leaves.
• Version used in "Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments."

1.00

• initial program version.
• Computes a 3-approximation of the rooted SPR distance between each pair of input trees.
• Computes the exact rooted SPR distance with complexity O(3^k n), where k is the rooted SPR distance and n is the number of leaves.
• Option to compute the smallest rooted SPR distance between the first input tree and each of the remaining input trees, to approximate the unrooted SPR distance.
• Version used in "A Unifying View on Approximation and FPT of Agreement Forests."