On weighted multiway cuts in trees

DOI10.1007/BF01581691zbMath0805.05016OpenAlexW2073609181MaRDI QIDQ1334954

László A. Székely, Péter L. Erdős

Publication date: 26 September 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581691

zbMATH Keywords

dynamic programmingpolynomial time algorithmtreesmin-max theoremMenger's theoremduality in linear programmingmultiway cut problem

Mathematics Subject Classification ID

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

Related Items (10)

The computational complexity of calculating partition functions of optimal medians with Hamming distance ⋮ Links between maximum likelihood and maximum parsimony under a simple model of site substitution ⋮ Nonlinear formulations and improved randomized approximation algorithms for multicut problems ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Exact algorithms for a discrete metric labeling problem ⋮ Counting and sampling SCJ small parsimony solutions ⋮ Exact algorithms for a discrete metric labeling problem ⋮ Minimum multiway cuts in trees ⋮ An improved approximation algorithm of MULTIWAY CUT. ⋮ Multiway cut and integer flow problems in trees

Cites Work

• Unnamed Item
• Unnamed Item
• Decompositions of leaf-colored binary trees
• Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
• On the multiway cut polyhedron
• The Complexity of Multiterminal Cuts

This page was built for publication: On weighted multiway cuts in trees