Expander flows, geometric embeddings and graph partitioning
From MaRDI portal
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)
Recommendations
- Expander flows, geometric embeddings and graph partitioning
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- Graph partitioning using single commodity flows
- Graph partitioning using single commodity flows
Cited in
(61)- An O( n)-approximation algorithm for directed sparsest cut
- General variable neighborhood search for computing graph separators
- The bi-objective critical node detection problem
- SDP primal-dual approximation algorithms for directed hypergraph expansion and sparsest cut with product demands
- Crossing number, pair-crossing number, and expansion
- The geometry of graphs and some of its algorithmic applications
- Approximation algorithms via contraction decomposition
- On graph parameters guaranteeing fast sandpile diffusion
- Balanced partitions of trees and applications
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
- Cut problems in graphs with a budget constraint
- Fréchet embeddings of negative type metrics
- Inoculation strategies for victims of viruses and the sum-of-squares partition problem
- Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Graph densification
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- Approximation algorithms for the weighted t-uniform sparsest cut and some other graph partitioning problems
- A semidefinite programming approach to the hypergraph minimum bisection problem
- The complexity status of problems related to sparsest cuts
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
- On Khot’s unique games conjecture
- Asymptotic negative type properties of finite ultrametric spaces
- A derandomized approximation algorithm for the critical node detection problem
- A randomized algorithm with local search for containment of pandemic disease spread
- Expander graphs and their applications
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Linear time algorithms for approximating the facility terminal cover problem
- Unbalanced graph partitioning
- Fast balanced partitioning is hard even on grids and trees
- Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\)
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
- Approximation algorithms for finding maximum induced expanders
- Graph clustering
- On the advantage of overlapping clusters for minimizing conductance
- Brief announcement: Bounded-degree cut is fixed-parameter tractable
- Expander decomposition and pruning: faster, stronger, and simpler
- OPTIMAL FOLDING OF DATA FLOW GRAPHS BASED ON FINITE PROJECTIVE GEOMETRY USING VECTOR SPACE PARTITIONING
- Euclidean distortion and the sparsest cut
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Random walks, electric networks and the transience class problem of sandpiles
- Graph partitioning using single commodity flows
- Advances in metric embedding theory
- Expander flows, geometric embeddings and graph partitioning
- Graph partitioning using single commodity flows
- Moment inequalities for sums of random matrices and their applications in optimization
- Sum-of-squares lower bounds for densest k-subgraph
- On min-bisections of graphs
- Efficient partitioning algorithms for optimizing big graph computation
- A note on multiflows and treewidth
- An improved approximation ratio for the minimum linear arrangement problem
- Coarse differentiation and multi-flows in planar graphs
- \(\ell ^2_2\) spreading metrics for vertex ordering problems
- Approximation algorithms for requirement cut on graphs
- Spectral partitioning works: planar graphs and finite element meshes
- Clustering and outlier detection using isoperimetric number of trees
- Analysis of set-up time models: a metric perspective
- On average distortion of embedding metrics into the line
- Approximation algorithms for the Bipartite Multicut problem
This page was built for publication: Expander flows, geometric embeddings and graph partitioning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5901073)
