1. Classes of tree-based networks
- Author
-
Mareike Fischer, Michelle Galla, Lina Herbst, Yangjing Long, and Kristina Wicke
- Subjects
Phylogenetic tree ,Phylogenetic network ,Tree-based network ,Edge-based network ,Chordal network ,Hamilton connected ,Drawing. Design. Illustration ,NC1-1940 ,Computer applications to medicine. Medical informatics ,R858-859.7 ,Computer software ,QA76.75-76.765 - Abstract
Abstract Recently, so-called tree-based phylogenetic networks have attracted considerable attention. These networks can be constructed from a phylogenetic tree, called the base tree, by adding additional edges. The primary aim of this study is to provide sufficient criteria for tree-basedness by reducing phylogenetic networks to related graph structures. Even though it is generally known that determining whether a network is tree-based is an NP-complete problem, one of these criteria, namely edge-basedness, can be verified in linear time. Surprisingly, the class of edge-based networks is closely related to a well-known family of graphs, namely, the class of generalized series-parallel graphs, and we explore this relationship in full detail. Additionally, we introduce further classes of tree-based networks and analyze their relationships.
- Published
- 2020
- Full Text
- View/download PDF