4 papers · 1 filter
Characterizing and Transforming DAGs within the I-LCA Framework
Marc Hellmuth, Anna Lindeberg
We explore the connections between clusters and least common ancestors (LCAs) in directed acyclic graphs (DAGs), focusing on the interplay between so-called -lca-relevant DAGs a…
Simplifying and Characterizing DAGs and Phylogenetic Networks via Least Common Ancestor Constraints
Anna Lindeberg, Marc Hellmuth
Rooted phylogenetic networks, or more generally, directed acyclic graphs (DAGs), are widely used to model species or gene relationships that traditional rooted trees cannot fully c…
Network Representation and Modular Decomposition of Combinatorial Structures: A Galled-Tree Perspective
Anna Lindeberg, Guillaume E. Scholz, Marc Hellmuth
In phylogenetics, reconstructing rooted trees from distances between taxa is a common task. Böcker and Dress generalized this concept by introducing symbolic dated maps $δ:X \times…
Isomorphism Testing of Rooted Trees in Linear Time
Anna Lindeberg
The AHU-algorithm solves the computationally difficult graph isomorphism problem for rooted trees, and does so with a linear time complexity. Although the AHU-algorithm has remaine…