Anna LindebergPhD Student
About me
PhD student in computational mathematics. Scientific interests in graph theory and other discrete structures with an algorithmic focus; often motivated by genetic data and the study of evolution.
Teaching
Research
Recent papers
Simplifying and Characterizing DAGs and Phylogenetic Networks via Least Common Ancestor Constraints
A. Lindeberg , M. Hellmuth
Bulletin of Mathematical Biology, 2025
[arXiv] [publisher]
Network Representation and Modular Decomposition of Combinatorial Structures: A Galled-Tree Perspective
A. Lindeberg , G.E. Scholz, M. Hellmuth
Vietnam J. Math., Special Issue dedicated to Andreas Dress, Springer (to appear), 2025
[arXiv]
Preprints
Global Least Common Ancestor (LCA) Networks
A. Lindeberg, B. J. Schmidt, M. Changat, A. V. Shanavas, P. F. Stadler, M. Hellmuth
[arXiv]
Orthology and Near-Cographs in the Context of Phylogenetic Networks
A. Lindeberg, G. E. Scholz, N. Wieseke, M. Hellmuth
[arXiv]
Characterizing and Transforming DAGs within the I-LCA Framework
A. Lindeberg , M. Hellmuth
[arXiv]
Publications
A selection from Stockholm University publication database
-
Simplifying and Characterizing DAGs and Phylogenetic Networks via Least Common Ancestor Constraints
2025. Anna Lindeberg, Marc Hellmuth. Bulletin of Mathematical Biology 87 (3)
ArticleRead more about Simplifying and Characterizing DAGs and Phylogenetic Networks via Least Common Ancestor ConstraintsRooted phylogenetic networks, or more generally, directed acyclic graphs (DAGs), are widely used to model species or gene relationships that traditional rooted trees cannot fully capture, especially in the presence of reticulate processes or horizontal gene transfers. Such networks or DAGs are typically inferred from observable data (e.g., genomic sequences of extant species), providing only an estimate of the true evolutionary history. However, these inferred DAGs are often complex and difficult to interpret. In particular, many contain vertices that do not serve as least common ancestors (LCAs) for any subset of the underlying genes or species, thus may lack direct support from the observable data. In contrast, LCA vertices are witnessed by historical traces justifying their existence and thus represent ancestral states substantiated by the data. To reduce unnecessary complexity and eliminate unsupported vertices, we aim to simplify a DAG to retain only LCA vertices while preserving essential evolutionary information. In this paper, we characterize LCA -relevant and lca -relevant DAGs, defined as those in which every vertex serves as an LCA (or unique LCA) for some subset of taxa. We introduce methods to identify LCAs in DAGs and efficiently transform any DAG into an LCA -relevant or lca -relevant one while preserving key structural properties of the original DAG or network. This transformation is achieved using a simple operator "⊖" that mimics vertex suppression.
-
Construction of k-matchings in graph products
2022. Anna Lindeberg, Marc Hellmuth. The Art of Discrete and Applied Mathematics 6 (2)
ArticleRead more about Construction of k-matchings in graph productsA k-matching M of a graph G = (V,E) is a subset M ⊆ E such that each connected component in the subgraph F = (V,M) of G is either a single-vertex graph or k-regular, i.e., each vertex has degree k. In this contribution, we are interested in k-matchings in the four standard graph products: the Cartesian, strong, direct and lexicographic product.
As we shall see, the problem of finding non-empty k-matchings (k ≥ 3) in graph products is NP-complete. Due to the general intractability of this problem, we focus on different polynomial-time constructions of k-matchings in a graph product G ⋆ H that are based on kG-matchings MG and kH-matchings MH of its factors G and H, respectively. In particular, we are interested in properties of the factors that have to be satisfied such that these constructions yield a maximum k-matching in the respective products. Such constructions are also called “well-behaved” and we provide several characterizations for this type of k-matchings.
Our specific constructions of k-matchings in graph products satisfy the property of being weak-homomorphism preserving, i.e., constructed matched edges in the product are never “projected” to unmatched edges in the factors. This leads to the concept of weak-homomorphism preserving k-matchings. Although the specific k-matchings constructed here are not always maximum k-matchings of the products, they have always maximum size among all weak-homomorphism preserving k-matchings. Not all weak-homomorphism preserving k-matchings, however, can be constructed in our manner. We will, therefore, determine the size of maximum-sized elements among allweak-homomorphism preserving k-matching within the respective graph products, provided that the matchings in the factors satisfy some general assumptions.
Show all publications by Anna Lindeberg at Stockholm University
$presentationText