A 2-Approximation Algorithm for the Directed Multiway Cut Problem

DOI10.1137/S009753979732147XzbMath1052.68103OpenAlexW2159454021MaRDI QIDQ2784466

Joseph (Seffi) Naor, Leonid Zosin

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753979732147x

zbMATH Keywords

combinatorial optimizationdirected graphapproximation algorithmsmulticommodity flowmultiway cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (12)

The maximum integer multiterminal flow problem in directed graphs ⋮ An improved parameterized algorithm for the minimum node multiway cut problem ⋮ Global and fixed-terminal cuts in digraphs ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Clique Cover and Graph Separation ⋮ Vertex downgrading to minimize connectivity ⋮ Algorithms for Multiterminal Cuts ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ A simple algorithm for the multiway cut problem ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ Unnamed Item

This page was built for publication: A 2-Approximation Algorithm for the Directed Multiway Cut Problem