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)

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

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., 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