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

Erdős, Péter and Székely, L.A. (1992) Evolutionary trees: An integer multicommodity max-flow-min-cut theorem. ADVANCES IN APPLIED MATHEMATICS, 13 (4). pp. 375-389. ISSN 0196-8858

Text ErdosSzekely-AAM92.pdf Restricted to Repository staff only Download (785kB) | Request a copy

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.

Actions (login required)

Edit Item