Sparsest cuts and bottlenecks in graphs

DOI10.1016/0166-218X(90)90133-WzbMath0733.05056OpenAlexW1989720410MaRDI QIDQ810053

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

zbMATH Keywords

networkNP-hardsparsest cutbottlenecks

Mathematics Subject Classification ID

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

Related Items (27)

A Mixed Integer Model for the Sparsest 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 ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Isoperimetric inequalities in simplicial complexes ⋮ Convergence and synchronization in networks of piecewise-smooth systems via distributed discontinuous coupling ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Optimal sufficient requirements on the embedded Ising problem in polynomial time ⋮ On Canonical Concurrent Flows, Crossing Number and Graph Expansion ⋮ Improved approximations for the minimum-cut ratio and the flux ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Graph clustering ⋮ Sparsest cuts and concurrent flows in product graphs. ⋮ Employee workload balancing by graph partitioning ⋮ Bounds on maximum concurrent flow in random bipartite graphs ⋮ The Complexity Status of Problems Related to Sparsest Cuts ⋮ Polynomiality of sparsest cuts with fixed number of sources ⋮ 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 ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ NP-hardness of Euclidean sum-of-squares clustering ⋮ Bounds on isoperimetric values of trees ⋮ Convex programming based spectral clustering ⋮ Linear time algorithms for finding sparsest cuts in various graph classes ⋮ A structured family of clustering and tree construction methods ⋮ Column-generation based bounds for the homogeneous areas problem

Cites Work

• The maximum concurrent flow problem
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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