Sparsest cuts and bottlenecks in graphs
From MaRDI portal
Publication:810053
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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Operations research and management science (90B99) Connectivity (05C40)
Related Items
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
