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

Péter L. Erdös, László A. Szekely

Research output: Contribution to journalArticleAcademic

19 Citations (Scopus)
100 Downloads (Pure)


In biomathematics, the extensions of a leaf-colouration of a binary tree to the whole vertex set with minimum number of colour-changing edges are extensively studied. Our paper generalizes the problem for trees; algorithms and a Menger-type theorem are presented. The LP dual of the problem is a multicommodity flow problem, for which a max-flow-min-cut theorem holds. The problem that we solve is an instance of the NP-hard multiway cut problem.
Original languageEnglish
Pages (from-to)375-389
JournalAdvances in Applied Mathematics
Issue number4
Publication statusPublished - 1992


  • IR-57455


Dive into the research topics of 'Evolutionary trees: an integer multicommodity max-flow-min-cut theorem'. Together they form a unique fingerprint.

Cite this