An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut

DOI10.1016/j.ipl.2005.10.005zbMath1184.68637OpenAlexW2045675568MaRDI QIDQ1045922

Harald Räcke, Mohammad Taghi Hajiaghayi

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.10.005

zbMATH Keywords

directed graphsapproximation algorithmsmulticommodity flowsparsest cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (5)

Cut-sufficient directed 2-commodity multiflow topologies ⋮ Temporal flows in temporal networks ⋮ Bounds on maximum concurrent flow in random bipartite graphs ⋮ Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs ⋮ Quasimetric embeddings and their applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound on the integrality gap for minimum multicut in directed networks
• Minimal multicut and maximal integer multiflow: a survey
• On the Max-flow min-cut ratio for directed multicommodity flows
• Approximating directed multicuts
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• Greedy approximation algorithms for directed multicuts
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut