On weighted multiway cuts in trees
From MaRDI portal
Publication:1334954
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
dynamic programming; polynomial time algorithm; trees; min-max theorem; Menger's theorem; duality in linear programming; multiway cut problem
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