On weighted multiway cuts in trees

DOI10.1007/BF01581691zbMath0805.05016MaRDI 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 programming; polynomial time algorithm; trees; min-max theorem; Menger's theorem; duality in linear programming; multiway cut problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C05: Trees

90C27: Combinatorial optimization

90C39: Dynamic programming

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

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