Polynomial flow-cut gaps and hardness of directed cut problems

DOI10.1145/1502793.1502795zbMath1325.68096OpenAlexW1974018476MaRDI QIDQ3452200

Sanjeev Khanna, Julia Chuzhoy

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

hardness of approximationsparsest cutdirected multicut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21)

Related Items (8)

Vertical perimeter versus horizontal perimeter ⋮ The all-or-nothing flow problem in directed graphs with symmetric demand pairs ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ Bounds on maximum concurrent flow in random bipartite graphs ⋮ Evader interdiction: algorithms, complexity and collateral damage ⋮ The checkpoint problem ⋮ Quasimetric embeddings and their applications ⋮ Multicommodity flows and cuts in polymatroidal networks

This page was built for publication: Polynomial flow-cut gaps and hardness of directed cut problems