Hardness of cut problems in directed graphs

DOI10.1145/1132516.1132593MaRDI QIDQ2931415zbMATH OpenOpenAlexFDO

Authors Julia Chuzhoy, Sanjeev Khanna

Publication date 25 November 2014

Published in Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1132516.1132593

zbMATH Keywords

directed multicuthardness of approximationsparsest cut

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Polynomial flow-cut gaps and hardness of directed cut problems
• On the hardness of approximating Multicut and Sparsest-Cut
• A 2-approximation algorithm for the directed multiway cut problem
• Approximating multicut and the demand graph
• Approximation and Online Algorithms

Cited in

(20)

• Max Horn SAT and the minimum cut problem in directed hypergraphs
• Quasimetric embeddings and their applications
• Beating the 2-approximation factor for global bicut
• On the hardness of approximating Multicut and Sparsest-Cut
• New results on planar and directed multicuts
• Hardness of Graph Pricing Through Generalized Max-Dicut
• Polynomial flow-cut gaps and hardness of directed cut problems
• scientific article; zbMATH DE number 2079369 (Why is no real title available?)
• Approximating multicut and the demand graph
• On the advantage of overlapping clusters for minimizing conductance
• Minimum scan cover with angular transition costs
• Global and fixed-terminal cuts in digraphs
• Improved hardness for cut, interdiction, and firefighter problems
• Odd Multiway Cut in Directed Acyclic Graphs
• Finding and using directed cuts of real graphs of algorithms
• A lower bound on the integrality gap for minimum multicut in directed networks
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Most balanced minimum cuts
• Approximation algorithms for the Bipartite Multicut problem

This page was built for publication: Hardness of cut problems in directed graphs

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