An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
type: Item
instance of: scholarly article
title: An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
zbMATH Open document ID: 1184.68637
author: Harald Räcke
author: Mohammad T. Hajiaghayi
published in: Information Processing Letters
publication date: 2009-12-18T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5650190
zbMATH Keywords: approximation algorithms
zbMATH Keywords: directed graphs
zbMATH Keywords: sparsest cut
zbMATH Keywords: multicommodity flow
MaRDI profile type: Publication
full work available at URL: j.ipl.2005.10.005
OpenAlex ID: W2045675568
cites work: O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
cites work: Expander flows, geometric embeddings and graph partitioning
cites work: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
cites work: Approximating directed multicuts
cites work: Minimal multicut and maximal integer multiflow: a survey
cites work: Q4471328
cites work: On the Max-flow min-cut ratio for directed multicommodity flows
cites work: Greedy approximation algorithms for directed multicuts
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: A lower bound on the integrality gap for minimum multicut in directed networks
cites work: Q5501283
DOI: 10.1016/J.IPL.2005.10.005
Recommended article: Approximation and Online Algorithms
Recommended article: Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
Recommended article: $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
Recommended article: Approximating Sparsest Cut in Graphs of Bounded Treewidth
Recommended article: Greedy approximation algorithms for directed multicuts
Recommended article: An exact algorithm for MAX-CUT in sparse graphs
Recommended article: A 2-approximation algorithm for the directed multiway cut problem
Recommended article: Combinatorial approximation algorithms for the maximum directed cut problem
Recommended article: Linear time algorithms for finding sparsest cuts in various graph classes
Recommended article: Sparsest cut on bounded treewidth graphs
description: scientific article; zbMATH DE number 5650190