Min-max multiway cut

DOI10.1007/978-3-540-27821-4_19MaRDI QIDQ5313023zbMATH OpenOpenAlexFDO

Authors Zoya Svitkina, Éva Tardos

Publication date 25 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 1775387
• The multi-multiway cut problem
• An improved approximation algorithm of MULTIWAY CUT.
• A polynomial-time approximation scheme for planar multiway cut
• The multi-multiway cut problem

Cited in

(23)

• Minimum multiway cuts in trees
• _p-norm multiway cut
• An approximation algorithm for vehicle routing with compatibility constraints
• Parameterized algorithms for min-max multiway cut and list digraph homomorphism
• Cut problems in graphs with a budget constraint
• Unbalanced graph cuts with minimum capacity
• Maximum cuts for a minimum flow
• Bounded size graph clustering with applications to stream processing
• Submodular Cost Allocation Problem and Applications
• Cut Problems in Graphs with a Budget Constraint
• Online Maximum Directed Cut
• Unbalanced graph partitioning
• Packing multiway cuts in capacitated graphs
• Multiway cuts in node weighted graphs
• Spanning tree congestion and computation of generalized Győri-Lovász partition
• Local distribution and the symmetry gap: approximability of multiway partitioning problems
• A polynomial-time approximation scheme for planar multiway cut
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Posimodular function optimization
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Minimum shared‐power edge cut
• \(\ell_p\)-norm multiway cut
• A new approximation algorithm for the unbalanced min s-t cut problem

This page was built for publication: Min-max multiway cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5313023)