EVOLUTIONARY TREES - AN INTEGER MULTICOMMODITY MAX-FLOW - MIN-CUT THEOREM

被引：17

作者：

ERDOS, PL

SZEKELY, LA

机构：

[1] HUNGARIAN ACAD SCI, H-1364 BUDAPEST, HUNGARY

[2] EOTVOS LORAND UNIV, DEPT COMP SCI, H-1088 BUDAPEST, HUNGARY

来源：

ADVANCES IN APPLIED MATHEMATICS | 1992年 / 13卷 / 04期

关键词：

D O I：

10.1016/0196-8858(92)90017-Q

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. © 1992.

引用

页码：375 / 389

页数：15

共 11 条

[1] ON THE DISTRIBUTION OF LENGTHS OF EVOLUTIONARY TREES [J].