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

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

Research output: Contribution to journalArticleAcademic

18 Citations (Scopus)
70 Downloads (Pure)

Abstract

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
Volume13
Issue number4
DOIs
Publication statusPublished - 1992

Keywords

  • IR-57455

Fingerprint

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

Cite this