Sparsest cuts and bottlenecks in graphs

DOI10.1016/0166-218X(90)90133-WzbMATH Open0733.05056OpenAlexW1989720410MaRDI QIDQ810053FDOQ810053

Authors: David W. Matula, Farhad Shahrokhi 

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90133-w

Recommendations

• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Sparsest cuts and concurrent flows in product graphs.
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• The complexity status of problems related to sparsest cuts
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts

zbMATH Keywords

networkNP-hardsparsest cutbottlenecks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Connectivity (05C40) Operations research and management science (90B99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The maximum concurrent flow problem
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Title not available (Why is that?)

Cited In (32)

• A mixed integer model for the sparsest cut problem
• Linear time algorithms for finding sparsest cuts in various graph classes
• Bounds on isoperimetric values of trees
• Bounds on maximum concurrent flow in random bipartite graphs
• The complexity status of problems related to sparsest cuts
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
• Improved approximations for the minimum-cut ratio and the flux
• A structured family of clustering and tree construction methods
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Rational solutions of the graphsack problem
• Convex programming based spectral clustering
• The complexity of finding uniform sparsest cuts in various graph classes
• Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
• A linear time algorithm for graph partition problems
• Column-generation based bounds for the homogeneous areas problem
• Optimal sufficient requirements on the embedded Ising problem in polynomial time
• Employee workload balancing by graph partitioning
• On Canonical Concurrent Flows, Crossing Number and Graph Expansion
• Convergence and synchronization in networks of piecewise-smooth systems via distributed discontinuous coupling
• Partitioning well-clustered graphs: spectral clustering works!
• Sparsest cuts and concurrent flows in product graphs.
• Integrality gaps for sparsest cut and minimum linear arrangement problems
• Mean isoperimetry with control on outliers: exact and approximation algorithms
• Isoperimetric inequalities in simplicial complexes
• Graph clustering
• Polynomiality of sparsest cuts with fixed number of sources
• Extremal cuts of sparse random graphs
• All-Pairs Min-Cut in Sparse Networks
• NP-hardness of Euclidean sum-of-squares clustering
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time

This page was built for publication: Sparsest cuts and bottlenecks in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810053)