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), 2024
[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
-
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