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

DOI10.1016/0196-8858(92)90017-QMaRDI QIDQ1802347zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On weighted multiway cuts in trees
• Decompositions of leaf-colored binary trees
• Minimizing phylogenetic number to find good evolutionary trees
• Multiway cut and integer flow problems in trees
• scientific article; zbMATH DE number 1088267

Cites work

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

Cited in

(10)

• On weighted multiway cuts in trees
• Minimum multiway cuts in trees
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• Five surprising properties of parsimoniously colored trees
• Evolutionary model for the Steiner tree problem with flow-dependent weights
• An evolutionary approach for finding optimal trees in undirected networks
• Algorithmic aspects of homophyly of networks
• Exact algorithms for a discrete metric labeling problem
• Exact algorithms for a discrete metric labeling problem
• A parsimony-based metric for phylogenetic trees

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

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