Inferring DAGs and phylogenetic networks from least common ancestors
Abstract
A least common ancestor (LCA) of two leaves in a directed acyclic graph (DAG) is a vertex that is an ancestor of both leaves and has no proper descendant that is also their common ancestor. LCAs capture hierarchical relationships in rooted trees and, more generally, in DAGs. In 1981, Aho et al. introduced the problem of determining whether a set of pairwise LCA constraints on a set $X$, of the form $(i,j)
Fields of Study & Subjects
Genomics and Phylogenetic Studies
Genome Rearrangement Algorithms
Constraint Satisfaction and Optimization
Publication details
- Journal / source
- Theoretical Computer Science
- Volume
- 1082
- Pages
- 116114–116114
- Publication date
- 15 June 2026
- Language
- EN