Erdős, Péter and Székely, L.A. (1994) On weighted multiway cuts in trees. MATHEMATICAL PROGRAMMING, 65 (1-3). pp. 93-105. ISSN 0025-5610
![[img]](http://real.mtak.hu/style/images/fileicons/text.png) |
Text
ErdosSzekely-MP94.pdf Restricted to Repository staff only Download (769kB) | Request a copy |
Abstract
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. © 1994 The Mathematical Programming Society, Inc.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Tree; Multiway cut; Menger's theorem; dynamic programming; Duality in linear programming; AMS 1991 Subject Classifications: 05C05, 05C70, 90C27 |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 06 Feb 2014 07:50 |
| Last Modified: | 06 Feb 2014 07:50 |
| URI: | http://real.mtak.hu/id/eprint/9927 |
Actions (login required)
 |
Edit Item |
