ON WEIGHTED MULTIWAY CUTS IN TREES

被引：23

作者：

ERDOS, PL

SZEKELY, LA

机构：

[1] HUNGARIAN ACAD SCI, INST MATH, H-1055 BUDAPEST, HUNGARY

[2] UNIV NEW MEXICO, DEPT MATH, ALBUQUERQUE, NM 87131 USA

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

来源：

MATHEMATICAL PROGRAMMING | 1994年 / 65卷 / 01期

关键词：

MULTIWAY CUT; MENGER THEOREM; TREE; DUALITY IN LINEAR PROGRAMMING; DYNAMIC PROGRAMMING;

D O I：

10.1007/BF01581691

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A min-max theorem is developed for the multiway cut problem of edge-weighted trees. We present a polynomial time algorithm to construct an optimal dual solution, if edge weights come in unary representation. Applications to biology also require some more complex edge weights. We describe a dynamic programming type algorithm for this more general problem from biology and show that our min-max theorem does not apply to it.

引用

页码：93 / 105

页数：13

共 12 条

[1] ON THE MULTIWAY CUT POLYHEDRON
CHOPRA, S
RAO, MR
[J]. NETWORKS, 1991, 21 (01) : 51 - 89
[2] Cunningham WH, 1991, DIMACS SERIES DISCRE, V5, P105, DOI 10.1090/dimacs/005/07
[3] DAHLHAUS E, 1983, COMPLEXITY MULTIWAY
[4] EVOLUTIONARY TREES - AN INTEGER MULTICOMMODITY MAX-FLOW - MIN-CUT THEOREM
ERDOS, PL
SZEKELY, LA
[J]. ADVANCES IN APPLIED MATHEMATICS, 1992, 13 (04) : 375 - 389
[5] ERDOS PL, 1992, INTEGER PROGRAMMING, P334
[6] TOWARD DEFINING COURSE OF EVOLUTION - MINIMUM CHANGE FOR A SPECIFIC TREE TOPOLOGY
FITCH, WM
[J]. SYSTEMATIC ZOOLOGY, 1971, 20 (04): : 406 - &
[7] MINIMUM MUTATION FITS TO A GIVEN TREE
HARTIGAN, JA
[J]. BIOMETRICS, 1973, 29 (01) : 53 - 65
[8] Menger K., 1927, FUND MATH, V10, P96, DOI DOI 10.4064/FM-10-1-96-115
[9] MENHAUSER GL, 1988, INTEGER COMBINATORIA
[10] Sankoff D., 1983, TIME WARPS STRING ED, P253

← 1 2 →