Approximating directed multicuts

DOI10.1007/S00493-005-0015-5MaRDI QIDQ2387182zbMATH OpenOpenAlexFDO

Authors Rabani Yuval, Joseph Cheriyan, Howard Karloff

Publication date 26 January 2006

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-005-0015-5

zbMATH Keywords

approximation guaranteespolynomial-time algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Review text

The authors consider the problem of finding a minimum multicut in a directed multicommodity flow network. The first nontrivial upper bounds on the max flow-to-min multicut ratio are obtained. These results are algorithmic, demonstrating nontrivial approximation guarantees.

Recommendations

• scientific article; zbMATH DE number 2079369
• Approximation and Online Algorithms
• Greedy approximation algorithms for directed multicuts
• On the Max-flow min-cut ratio for directed multicommodity flows
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications

Cited in

(16)

• An O( n)-approximation algorithm for directed sparsest cut
• Approximating minimum feedback sets and multicuts in directed graphs
• Quasimetric embeddings and their applications
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Polynomial flow-cut gaps and hardness of directed cut problems
• Approximate max-integral-flow/min-multicut theorems
• Online Maximum Directed Cut
• scientific article; zbMATH DE number 2079369 (Why is no real title available?)
• On the advantage of overlapping clusters for minimizing conductance
• Register loading via linear programming
• Greedy approximation algorithms for directed multicuts
• Approximation and Online Algorithms
• On the parameterized complexity of symmetric directed multicut
• A lower bound on the integrality gap for minimum multicut in directed networks
• The checkpoint problem
• The multi-multiway cut problem

This page was built for publication: Approximating directed multicuts

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