Complexity of modification problems for best match graphs
From MaRDI portal
Publication:2661779
DOI10.1016/j.tcs.2021.02.037zbMath1500.92068arXiv2006.16909OpenAlexW3130550583MaRDI QIDQ2661779
Peter F. Stadler, Marc Hellmuth, David Schaller
Publication date: 8 April 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2006.16909
Related Items
Least resolved trees for two-colored best match graphs ⋮ Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees ⋮ Quasi-best match graphs ⋮ The structure of 2-colored best match graphs ⋮ Indirect identification of horizontal gene transfer ⋮ Best match graphs with binary trees
Cites Work
- Unnamed Item
- Kernel and fast algorithm for dense triplet inconsistency
- Complexity and parameterized algorithms for cograph editing
- New results on optimizing rooted triplets consistency
- Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
- Orthology relations, symbolic ultrametrics, and cographs
- Complexity of modification problems for reciprocal best match graphs
- Reciprocal best match graphs
- Best match graphs and reconciliation of gene trees with species trees
- Best match graphs
- Complete characterization of incorrect orthology assignments in best match graphs
- The Graph Menagerie: Abstract Algebra and the Mad Veterinarian
- Finding a maximum likelihood tree is hard
- The complexity of some edge deletion problems
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Computing the Minimum Fill-In is NP-Complete
- Algorithms on Strings, Trees and Sequences
- Reducibility among Combinatorial Problems
- Complexity classification of some edge modification problems
- Generating a random sink-free orientation in quadratic time
