Two strikes against perfect phylogeny

DOI10.1007/3-540-55719-9_80zbMath1425.68136OpenAlexW2134766004WikidataQ56430104 ScholiaQ56430104MaRDI QIDQ5204323

Michael R. Fellows, Tandy J. Warnow, Hans L. Bodlaender

Publication date: 4 December 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: http://dspace.library.uu.nl/handle/1874/16653

zbMATH Keywords

perfect phylogeny

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Biochemistry, molecular biology (92C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ⋮ Computing the unrooted maximum agreement subtree in sub-quadratic time ⋮ Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Efficient approximation of convex recolorings ⋮ Trees, taxonomy, and strongly compatible multi-state characters ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ Optimizing tree and character compatibility across several phylogenetic trees ⋮ Chordal bipartite completion of colored graphs ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ A simple characterization of the minimal obstruction sets for three-state perfect phylogenies ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Recovering trees from well-separated multi-state characters. ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Convex recolorings of strings and trees: Definitions, hardness results and algorithms ⋮ Advice classes of parametrized tractability ⋮ On the complexity of computing treebreadth ⋮ Intervalizing k-colored graphs ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Completing colored graphs to meet a target property ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ On intervalizing \(k\)-colored graphs for DNA physical mapping ⋮ Minimizing phylogenetic number to find good evolutionary trees ⋮ On the approximability of the Steiner tree problem in phylogeny ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ On computing graph minor obstruction sets ⋮ Identifying phylogenetic trees ⋮ Matrix sandwich problems ⋮ Unnamed Item ⋮ Myhill-Nerode Methods for Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperedge replacement: grammars and languages
• On rigid circuit graphs
• Separating subgraphs in k-trees: Cables and caterpillars
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The Steiner problem in phylogeny is NP-complete
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• An idealized concept of the true cladistic character
• A mathematical foundation for the analysis of cladistic character compatibility
• On the compatibility of binary qualitative taxonomic characters
• An algebraic analysis of cladistic characters
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On simple characterizations of k-trees
• A characterisation of rigid circuit graphs
• Graph minors. XIII: The disjoint paths problem
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
• Representation of a finite graph by a set of intervals on the real line
• Easy problems for tree-decomposable graphs
• Complexity of Finding Embeddings in a k-Tree
• Inferring Evolutionary History From DNA Sequences
• The pathwidth and treewidth of cographs
• Efficient algorithms for inferring evolutionary trees