Classes of tree-based networks

摘要

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.