Computing the edge expansion of a graph using semidefinite programming
From MaRDI portal
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Semidefinite programming (90C22) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- A thermodynamically motivated simulation procedure for combinatorial optimization problems
- Basic Facts about Expander Graphs
- BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
- Expander flows, geometric embeddings and graph partitioning
- Expander graphs and their applications
- Experiments in quadratic 0-1 programming
- Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations
- scientific article; zbMATH DE number 1182569 (Why is no real title available?)
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- On Dantzig figures from graded lexicographic orders
- On the expansion of combinatorial polytopes
- Parallel community detection for massive graphs
- Partitioning through projections: strong SDP bounds for large graph partition problems
- SDP-based bounds for graph partition via extended ADMM
- Semidefinite programming based algorithms for the sparsest cut problem
- Semidefinite programming relaxations for the graph partitioning problem
- Some simplified NP-complete graph problems
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
This page was built for publication: Computing the edge expansion of a graph using semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7030730)
