Two strikes against perfect phylogeny
From MaRDI portal
Publication:5204323
DOI10.1007/3-540-55719-9_80zbMATH Open1425.68136OpenAlexW2134766004WikidataQ56430104 ScholiaQ56430104MaRDI QIDQ5204323FDOQ5204323
Authors: Michael R. Fellows, Hans L. Bodlaender, Tandy J. Warnow 
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
Recommendations
Biochemistry, molecular biology (92C40) Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Hyperedge replacement: grammars and languages
- The Steiner problem in phylogeny is NP-complete
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Graph minors. XIII: The disjoint paths problem
- Incidence matrices and interval graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- On rigid circuit graphs
- 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 intersection graphs of subtrees in trees are exactly the chordal graphs
- Representation of a finite graph by a set of intervals on the real line
- On simple characterizations of k-trees
- Triangulated graphs and the elimination process
- Efficient algorithms for inferring evolutionary trees
- A mathematical foundation for the analysis of cladistic character compatibility
- Title not available (Why is that?)
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- The pathwidth and treewidth of cographs
- A Simple Linear Time Algorithm for Triangulating Three-Colored Graphs
- A characterisation of rigid circuit graphs
- Title not available (Why is that?)
- Inferring Evolutionary History From DNA Sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Separating subgraphs in k-trees: Cables and caterpillars
- Title not available (Why is that?)
- Title not available (Why is that?)
- An idealized concept of the true cladistic character
- On the compatibility of binary qualitative taxonomic characters
- An algebraic analysis of cladistic characters
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (43)
- Optimizing tree and character compatibility across several phylogenetic trees
- Identifying phylogenetic trees
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- On intervalizing \(k\)-colored graphs for DNA physical mapping
- Chordal bipartite completion of colored graphs
- Algorithms and complexity of sandwich problems in graphs (extended abstract)
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem
- On the approximability of the Steiner tree problem in phylogeny
- A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
- Convex recolorings of strings and trees: Definitions, hardness results and algorithms
- Matrix sandwich problems
- On computing graph minor obstruction sets
- On the Generalised Character Compatibility Problem for Non-branching Character Trees
- On the complexity of computing treebreadth
- Title not available (Why is that?)
- A colored graph approach to perfect phylogeny with persistent characters
- Minimizing phylogenetic number to find good evolutionary trees
- Completing colored graphs to meet a target property
- Advice classes of parametrized tractability
- A simple characterization of the minimal obstruction sets for three-state perfect phylogenies
- Bipartite completion of colored graphs avoiding chordless cycles of given lengths
- Some completion problems for graphs without chordless cycles of prescribed lengths
- On the approximability of the Steiner tree problem in phylogeny
- Unique perfect phylogeny is NP-hard
- On the Generality of Phylogenies from Incomplete Directed Characters
- Title not available (Why is that?)
- The three-state perfect phylogeny problem reduces to 2-SAT
- Compact navigation and distance oracles for graphs with small treewidth
- A novel insight into the perfect phylogeny problem
- Efficient approximation of convex recolorings
- The balanced connected subgraph problem for geometric intersection graphs
- Title not available (Why is that?)
- Generalizing the splits equivalence theorem and four gamete condition: Perfect phylogeny on three-state characters
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Unique perfect phylogeny is intractable
- Computing the unrooted maximum agreement subtree in sub-quadratic time
- Finding a perfect phylogeny from mixed tumor samples
- Trees, taxonomy, and strongly compatible multi-state characters
- A revisit of the scheme for computing treewidth and minimum fill-in
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- Recovering trees from well-separated multi-state characters.
- Intervalizing \(k\)-colored graphs
This page was built for publication: Two strikes against perfect phylogeny
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5204323)
