Tree containment with soft polytomies

DOI10.7155/JGAA.00565MaRDI QIDQ5084686zbMATH OpenOpenAlexFDO

Authors Matthias Bentert, Mathias Weller

Publication date 28 June 2022

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00565

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 7238964
• Locating a tree in a phylogenetic network
• Solving the tree containment problem for genetically stable networks in quadratic time
• Solving the tree containment problem for reticulation-visible networks in linear time
• Solving the tree containment problem in linear time for nearly stable phylogenetic networks

Cites work

• scientific article; zbMATH DE number 7238964 (Why is no real title available?)
• A decomposition theorem and two algorithms for reticulation-visible networks
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• Basic phylogenetic combinatorics.
• Complexity of automaton identification from given data
• Locating a tree in a phylogenetic network
• Locating a tree in a phylogenetic network in quadratic time
• ReCombinatorics. The algorithmics of ancestral recombination graphs and explicit phylogenetic networks. With contributions from Charles H. Langley, Yun S. Song and Yufeng Wu
• Reticulation-visible networks
• Seeing the trees and their branches in the network is hard
• Solving the tree containment problem for reticulation-visible networks in linear time
• Topology of viral evolution

Cited in

(6)

• Locating a tree in a phylogenetic network
• scientific article; zbMATH DE number 7238964 (Why is no real title available?)
• A QUBO formulation for the tree containment problem
• scientific article; zbMATH DE number 756707 (Why is no real title available?)
• The watering of tall trees -- embolization and recovery
• Tree containment and degree conditions

Describes a project that uses

Uses Software

• S-Cluster++
• tcp_package

This page was built for publication: Tree containment with soft polytomies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084686)