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 t...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 edgebased 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.展开更多
Following publication of the original article[1],in the description of the leaf shrinking procedure as well as in Algorithm 1 and the definition of edge-based graphs in[1],the condition that G contains at least two le...Following publication of the original article[1],in the description of the leaf shrinking procedure as well as in Algorithm 1 and the definition of edge-based graphs in[1],the condition that G contains at least two leaves(i.e.,the condition|VL(G)|≥2)needs to be omitted.展开更多
基金funded by the state Mecklenburg-Western Pomerania by the Landesgraduierten-Studentshipfunded by the University of Greifswald by the Bogislaw-Studentshipfunded by the German Academic Scholarship Foundation by a studentship.
文摘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 edgebased 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.
文摘Following publication of the original article[1],in the description of the leaf shrinking procedure as well as in Algorithm 1 and the definition of edge-based graphs in[1],the condition that G contains at least two leaves(i.e.,the condition|VL(G)|≥2)needs to be omitted.
