×

On weighted multiway cuts in trees. (English) Zbl 0805.05016

Authors’ 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.

MSC:

05C05 Trees
90C39 Dynamic programming
90C35 Programming involving graphs or networks
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Chopra and M.R. Rao, ”On the multiway cut polyhedron,”Networks 21 (1991) 51–89. · Zbl 0746.90077 · doi:10.1002/net.3230210106
[2] W.H. Cunningham, ”The optimal multiterminal cut problem,”DIMACS Series in Discrete Math. 5 (1991) 105–120. · Zbl 0821.90125
[3] E. Dahlhaus, D.S. Johnson, C.H. Papadimitriou, P. Seymour and M. Yannakakis, ”The complexity of multiway cuts,” extended abstract (1983). · Zbl 0809.68075
[4] P.L. Erdos and L.A. Székely, ”Evolutionary trees: an integer multicommodity max–flow-min–cut theorem,”Advances in Applied Mathematics 13 (1992) 375–389. · Zbl 0773.05047 · doi:10.1016/0196-8858(92)90017-Q
[5] P.L. Erdos and L.A. Székely, ”Algorithms and min–max theorems for certain multiway cut,” in: E. Balas, G. Cornuéjols and R. Kannan, eds.,Integer Programming and Combinatorial Optimization, Proceedings of the Conference held at Carnegie Mellon University, May 25–27, 1992, by the Mathematical Programming Society (CMU Press, Pittsburgh, 1992) 334–345.
[6] W.M. Fitch, ”Towards defining the course of evolution. Minimum change for specific tree topology,”Systematic Zoology 20 (1971) 406–416. · doi:10.2307/2412116
[7] J.A. Hartigan, ”Minimum mutation fits to a given tree,”Biometrics 29 (1973) 53–65. · doi:10.2307/2529676
[8] L. Lovász and M.D. Plummer,Matching Theory (North-Holland, Amsterdam, 1986).
[9] K. Menger, ”Zur allgemeinen Kurventheorie,”Fundamenta Mathematicae 10 (1926)96–115 · JFM 53.0561.01
[10] G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (John Wiley & Sons, New York, 1988). · Zbl 0652.90067
[11] M. Steel, ”Decompositions of leaf-coloured binary trees,”Advances in Applied Mathematics 14 (1993) 1–24. · Zbl 0777.05047 · doi:10.1006/aama.1993.1001
[12] P.L. Williams and W.M. Fitch, ”Finding the minimal change in a given tree,” in: A. Dress and A. v. Haeseler, eds.,Trees and Hierarchical Structures, Lecture Notes in Biomathematics 84 (1989) 75–91.
[13] D. Sankoff and R.J. Cedergren, ”Simultaneous comparison of three or more sequences related by a tree,” in: D. Sankoff and J.B. Kruskal, eds.,Time Wraps, String Edits and Macromoleculas: The Theory and Practice of Sequence Comparison (Addison-Wesley, London, 1983) 253–263.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.