Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem

DOI10.1016/0196-8858(92)90017-QzbMath0773.05047OpenAlexW2085363210MaRDI QIDQ1802347

Péter L. Erdős, László A. Székely

Publication date: 18 October 1993

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

Full work available at URL: https://doi.org/10.1016/0196-8858(92)90017-q

zbMATH Keywords

binary treemulticommodity flowmultiway cut problemcolouration

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Related Items (8)

On weighted multiway cuts in trees ⋮ Five surprising properties of parsimoniously colored trees ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ Algorithmic aspects of homophyly of networks ⋮ Exact algorithms for a discrete metric labeling problem ⋮ Exact algorithms for a discrete metric labeling problem ⋮ Minimum multiway cuts in trees ⋮ A parsimony-based metric for phylogenetic trees

Cites Work

• Matching theory
• The Steiner problem in phylogeny is NP-complete
• Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
• Distributions on bicoloured binary trees arising from the principle of parsimony
• On the Distribution of Lengths of Evolutionary Trees
• On the multiway cut polyhedron
• The Complexity of Multiterminal Cuts

This page was built for publication: Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem