Hardness of cut problems in directed graphs

DOI10.1145/1132516.1132593zbMath1301.68155OpenAlexW2153164535MaRDI QIDQ2931415

Sanjeev Khanna, Julia Chuzhoy

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

hardness of approximationsparsest cutdirected multicut

Mathematics Subject Classification ID

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

Related Items (7)

On the advantage of overlapping clusters for minimizing conductance ⋮ On the complexity of the multicut problem in bounded tree-width graphs and digraphs ⋮ Most balanced minimum cuts ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ Quasimetric embeddings and their applications ⋮ Minimum Scan Cover with Angular Transition Costs ⋮ New results on planar and directed multicuts

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