A branch-&-price approach to the unrooted maximum agreement forest problem
<|reference_start|>A branch-&-price approach to the unrooted maximum agreement forest problem: We propose the first branch-&-price algorithm for the maximum agreement forest problem on unrooted binary trees: given two unrooted X-labelled binary trees we seek to partition X into a minimum number of blocks such that the induced subtrees are disjoint and have the same topologies in both trees. We provide a dynamic programming algorithm for the weighted maximum agreement subtree problem to solve the pricing problem. When combined with rigorous polynomial-time pre-processing our branch-&-price algorithm exhibits (beyond) state-of-the-art performance.<|reference_end|>
@article{frohn2024a,
    title={A branch-&-price approach to the unrooted maximum agreement forest
  problem},
    author={Martin Frohn, Steven Kelk, Simona Vychytilova},
    journal={arXiv preprint arXiv:2410.04122},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.04122},
    primaryClass={cs.DS math.OC q-bio.PE}
}