A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
From MaRDI portal
Publication:4376199
DOI10.1137/S0097539794279067zbMath0885.68073MaRDI QIDQ4376199
Sampath Kannan, Tandy J. Warnow
Publication date: 10 February 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794279067
dynamic programming; combinatorial enumeration; evolutionary trees; perfect phylogeny; polynomial delay algorithms
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C30: Enumeration in graph theory
68W10: Parallel algorithms in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples, A simple characterization of the minimal obstruction sets for three-state perfect phylogenies, Tree reconstruction from multi-state characters, Parameterized enumeration, transversals, and imperfect phylogeny reconstruction, Improved approximation algorithm for convex recoloring of trees, Convex recolorings of strings and trees: Definitions, hardness results and algorithms, PULLPRU: a practical approach to estimate phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion, Character-based phylogeny construction and its application to tumor evolution, Sharp upper and lower bounds on a restricted class of convex characters, Enumeration of binary trees compatible with a perfect phylogeny, Finding optimal triangulations parameterized by edge clique cover, Efficient approximation of convex recolorings
