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

No abstract is available for this paper.

• Publication year

  2006

• Venue

  Information Processing Letters

• Publication date

  2006-02-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.ipl.2005.10.005
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the max-flow min-cut ratio for directed multicommodity flows

  2006cited by this paper
• Minimal multicut and maximal integer multiflow: A survey

  2005cited by this paper
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut

  2005cited by this paper
• Greedy approximation algorithms for directed multicuts

  2005cited by this paper
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

  2005cited by this paper
• Expander flows, geometric embeddings and graph partitioning

  2004cited by this paper
• A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks

  2004cited by this paper
• Graph decomposition and a greedy algorithm for edge-disjoint paths

  2004influential reference
• Improved results for directed multicut

  2003influential reference
• Approximating Directed Multicuts

  2001cited by this paper
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

  1999cited by this paper
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• Cut problems and their application to divide-and-conquer

  1996cited by this paper

• Cut-sufficient directed 2-commodity multiflow topologies

  2025cites this paper
• Bounds on maximum concurrent flow in random bipartite graphs

  2020cites this paper
• D S ] 2 0 Ja n 20 17 Temporal flows in Temporal networks ⋆ , ⋆ ⋆

  2018cites this paper
• Quasimetric Embeddings and Their Applications

  2016cites this paper
• Temporal Flows in Temporal Networks

  2016cites this paper
• Flows in Temporal networks

  2016cites this paper
• Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries

  2013cites this paper
• Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs

  2012cites this paper
• Reformulation and cutting-plane approaches for solving two-stage optimization and network interdiction problems

  2011cites this paper
• Protein-Protein Interaction Network Evaluation for Identifying Potential Drug Targets

  2010influential citation
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries

  2009cites this paper
• Cycle-based algorithms for multicommodity network flow problems with separable piecewise convex costs

  2008cites this paper
• On the capacity of information networks

  2006cites this paper
• Directed metrics and directed graph partitioning problems

  2006influential citation
• On the capacity of information networks

  2006cites this paper
• Oblivious routing on node-capacitated and directed graphs

  2005cites this paper