O( n) approximation to sparsest cut in O(n^2) time
From MaRDI portal
Publication:3053148
Recommendations
Cited in
(29)- An O( n)-approximation algorithm for directed sparsest cut
- UPGMA and the normalized equidistant minimum evolution problem
- \(d\)-dimensional arrangement revisited
- Convergence and synchronization in networks of piecewise-smooth systems via distributed discontinuous coupling
- Mean isoperimetry with control on outliers: exact and approximation algorithms
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- The complexity status of problems related to sparsest cuts
- Connectivity oracles for graphs subject to vertex failures
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- The complexity of finding uniform sparsest cuts in various graph classes
- scientific article; zbMATH DE number 6850401 (Why is no real title available?)
- Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs
- On the advantage of overlapping clusters for minimizing conductance
- The normalized graph cut and Cheeger constant: from discrete to continuous
- Cheeger-type approximation for sparsest st-cut
- Organisational hierarchy constructions with easy Kuramoto synchronisation
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Euclidean distortion and the sparsest cut
- scientific article; zbMATH DE number 7539923 (Why is no real title available?)
- Graph partitioning using single commodity flows
- Expander flows, geometric embeddings and graph partitioning
- Graph partitioning using single commodity flows
- Expander flows, geometric embeddings and graph partitioning
- Combinatorial Fiedler theory and graph partition
- An Escape Time Formulation for Subgraph Detection and Partitioning of Directed Graphs
- A simpler and parallelizable \(O(\sqrt{\log n})\)-approximation algorithm for \textsc{Sparsest Cut}
- Graph algorithm based submodular function for sparsest cut problem
- Submodular hypergraph partitioning: metric relaxations and fast algorithms via an improved cut-matching game
- O( n)-approximation algorithms for bipartiteness ratio
This page was built for publication: \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3053148)
