Sparsest cuts and bottlenecks in graphs
From MaRDI portal
Publication:810053
DOI10.1016/0166-218X(90)90133-WzbMath0733.05056MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
90B99: Operations research and management science
05C40: Connectivity
Related Items
Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow, On Canonical Concurrent Flows, Crossing Number and Graph Expansion, Polynomial‐time algorithms for solving a class of critical node problems on trees and series‐parallel graphs, Improved approximations for the minimum-cut ratio and the flux, Partitioning Well-Clustered Graphs: Spectral Clustering Works!, Optimal sufficient requirements on the embedded Ising problem in polynomial time, The complexity of finding uniform sparsest cuts in various graph classes, Graph clustering, NP-hardness of Euclidean sum-of-squares clustering, Bounds on isoperimetric values of trees, A linear time algorithm for graph partition problems, Sparsest cuts and concurrent flows in product graphs., 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, Convex programming based spectral clustering, A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time, Bounds on maximum concurrent flow in random bipartite graphs, Column-generation based bounds for the homogeneous areas problem, Isoperimetric inequalities in simplicial complexes, Employee workload balancing by graph partitioning, Polynomiality of sparsest cuts with fixed number of sources, Convergence and synchronization in networks of piecewise-smooth systems via distributed discontinuous coupling, Mean isoperimetry with control on outliers: exact and approximation algorithms, A Mixed Integer Model for the Sparsest Cut problem, The Complexity Status of Problems Related to Sparsest Cuts, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, Linear time algorithms for finding sparsest cuts in various graph classes
Cites Work
