7 papers
Proximity Measures for Classes of Phylogenetic Networks
Leo van Iersel, Mark Jones, Esther Julien +2
Phylogenetic networks are used to represent the evolutionary history of species. Due to biological interpretations and computational advantages, researchers have focused on restric…
Constrained homomorphism orders
Jiri Fiala, Jan Hubicka, Yangjing Long
We study partial orders induced by constrained variants of finite graph homomorphisms: monomorphisms, embeddings, full homomorphisms, vertex-surjective, edge-surjective and surject…
The Quantum Homomorphism Orders are Universal
Yangjing Long
Quantum graph homomorphisms, introduced by Mančinska and Roberson, form a natural quantum relaxation of classical graph homomorphisms. Since this relaxation may create new comparab…
An Explicit Threshold for Attaining the Semple--Steel Bound with -State Characters
Peng Li, Yangjing Long
Let be the maximum, over all binary phylogenetic trees with leaves, of the minimum number of -state characters required to define the tree. Semple and Steel proved…
Exact Leaf Powers on Cycles, Ladders, Crowns, and Multipartite Block Graphs
Peng Li, Yangjing Long
Exact \(k\)-leaf powers are graphs whose edges are exactly the pairs of leaves at distance \(k\) in a tree. We prove explicit structure theorems for exact leaf powers on several re…
Computing the Arc-Deletion Distance to Orchard Networks is NP-hard
Peng Li, Zhiwei Liu, Yangjing Long
Phylogenetic networks generalize phylogenetic trees by allowing reticulate evolutionary events such as horizontal gene transfer and hybridization. Among the many subclasses of phyl…
Minimum Network Level Forced by Hardwired Cluster Data
Shilong Dai, Yangjing Long
Reticulate evolutionary events, such as hybridization, recombination, and horizontal transfer, can make a tree model inadequate. When evolutionary data are summarized as hardwired…