title: Characterization of the existence of galled-tree networks.
abstract: In this paper, we give a complete characterization of the existence of a galled-tree network in the form of simple sufficient and necessary conditions for both root-known and root-unknown cases. As a by-product we obtain a simple algorithm for constructing galled-tree networks. We also introduce a new necessary condition for the existence of a galled-tree network similar to bi-convexity.
authors.affiliation: School of Computing Science, Simon Fraser University, 8888 University Drive, Burnaby BC V5A 1S6, Canada. arvind@mitacs.ca
authors.forename: Arvind
authors.initials: A
authors.lastname: Gupta
authors.forename: Ján
authors.initials: J
authors.lastname: Manuch
authors.forename: Xiaohong
authors.initials: X
authors.lastname: Zhao
authors.forename: Ladislav
authors.initials: L
authors.lastname: Stacho
mesh_terms: D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D003198:Computer Simulation; D005787:Gene Frequency; D006239:Haplotypes / Q000235:genetics*; D008957:Models, Genetic; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D040641:Quantitative Trait Loci / Q000235:genetics*