2 citations · 6 across the 7 of their papers we have counts for
8 papers
The space of equidistant phylogenetic cactuses
Katharina T. Huber, Vincent Moulton, Megan Owen +2
We introduce and investigate the space of \emph{equidistant} -\emph{cactuses}. These are rooted, arc weighted, phylogenetic networks with leaf set , where is a finite set…
Maximum Covering Subtrees for Phylogenetic Networks
Nathan Davidov, Amanda Hernandez, Justin Jian +9
Tree-based phylogenetic networks, which may be roughly defined as leaf-labeled networks built by adding arcs only between the original tree edges, have elegant properties for model…
On the maximum agreement subtree conjecture for balanced trees
Magnus Bordewich, Simone Linz, Megan Owen +3
We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labelled trees on leaves have a maximum agreement subtree (MAST) of size at…
On Determining if Tree-based Networks Contain Fixed Trees
Maria Anaya, Olga Anipchenko-Ulaj, Aisha Ashfaq +9
We address an open question of Francis and Steel about phylogenetic networks and trees. They give a polynomial time algorithm to decide if a phylogenetic network, N, is tree-based…
Bounds on the Expected Size of the Maximum Agreement Subtree
Daniel Irving Bernstein, Lam Si Tung Ho, Colby Long +3
We prove polynomial upper and lower bounds on the expected size of the maximum agreement subtree of two random binary phylogenetic trees under both the uniform distribution and Yul…
Walks on SPR Neighborhoods
Alan Joseph J. Caceres, Juan Castillo, Jinnie Lee +1
A nearest-neighbor-interchange (NNI) walk is a sequence of unrooted phylogenetic trees, T_0, T_1, T_2,... where each consecutive pair of trees differ by a single NNI move. We give…
The Complexity of Finding Multiple Solutions to Betweenness and Quartet Compatibility
Maria Luisa Bonet, Simone Linz, Katherine St. John
We show that two important problems that have applications in computational biology are ASP-complete, which implies that, given a solution to a problem, it is NP-complete to decide…
Rotation Distance is Fixed-Parameter Tractable
Sean Cleary, Katherine St. John
Rotation distance between trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing ro…