Solving the tree containment problem in linear time for nearly stable phylogenetic networks

DOI10.1016/j.dam.2017.07.015zbMath1390.05083OpenAlexW2746724793WikidataQ58172937 ScholiaQ58172937MaRDI QIDQ1647836

Anthony Labarre, Louxin Zhang, Philippe Gambette, Stéphane Vialette, Andreas Dwi Maryanto Gunawan

Publication date: 27 June 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-01575001/file/DAM2017.pdf

zbMATH Keywords

phylogenetic treesphylogenetic networkstree containmentgenetically stable networksnearly stable networksreticulation visibility

Mathematics Subject Classification ID

Trees (05C05) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

Linear Time Algorithm for Tree-Child Network Containment ⋮ Non-essential arcs in phylogenetic networks ⋮ Classes of explicit phylogenetic networks and their biological and mathematical significance ⋮ Counting and enumerating tree-child networks and their subclasses ⋮ On cherry-picking and network containment

Uses Software

• PhyloNetwork
• tcp_package

Cites Work

• Unnamed Item
• Unnamed Item
• Reticulation-visible networks
• Phylogenetic networks that display a tree twice
• A decomposition theorem and two algorithms for reticulation-visible networks
• Seeing the trees and their branches in the network is hard
• Locating a tree in a phylogenetic network
• Solving the Tree Containment Problem for Genetically Stable Networks in Quadratic Time
• Locating a Tree in a Phylogenetic Network in Quadratic Time
• Phylogeny
• Topology of viral evolution

This page was built for publication: Solving the tree containment problem in linear time for nearly stable phylogenetic networks