Phylogenetic graph models beyond trees

DOI10.1016/j.dam.2008.06.031zbMath1163.92030OpenAlexW1970311713MaRDI QIDQ1026198

Ulrik Brandes, Sabine Cornelsen

Publication date: 24 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.06.031

zbMATH Keywords

compatibilityphylogenetic treesgraph modelssplitscactus model

Mathematics Subject Classification ID

Trees (05C05) Problems related to evolution (92D15) Applications of graph theory (05C90) Complexity and performance of numerical algorithms (65Y20)

Related Items

Uprooted phylogenetic networks ⋮ Computing consensus networks for collections of 1-nested phylogenetic networks ⋮ Level-1 phylogenetic networks and their balanced minimum evolution polytopes ⋮ Combinatorial Scoring of Phylogenetic Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A canonical decomposition theory for metrics on a finite set
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Modular decomposition and transitive orientation
• Canonical cactus representation for miminum cuts
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A fast algorithm for cactus representations of minimum cuts
• Characterizing Families of Cuts that can be Represented by Axis-Parallel Rectangles
• Three Partition Refinement Algorithms
• Algorithms on Strings, Trees and Sequences
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
• Combinatorial Pattern Matching
• Efficient algorithms for inferring evolutionary trees