A mixed integer model for the sparsest cut problem

DOI10.1016/J.ENDM.2010.05.015MaRDI QIDQ2883559zbMATH OpenOpenAlexFDO

Authors Eric Gourdin

Publication date 13 May 2012

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2010.05.015

zbMATH Keywords

maximum concurrent flowmixed integer modelssparsest cut

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27)

Recommendations

• Sparsest cuts and bottlenecks in graphs
• Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
• The maximum congested cut problem and its robust counterpart: Exact and approximation algorithms for the single and the multicommodity case
• An effective compact formulation of the max cut problem on sparse graphs

Cites work

• A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
• Approximate max-flow min-(multi)cut theorems and their applications
• scientific article; zbMATH DE number 4211829 (Why is no real title available?)
• Improved approximations for the minimum-cut ratio and the flux
• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• Multicommodity flows in planar graphs
• Sparsest cuts and bottlenecks in graphs

Cited in

(4)

• Sparsity of integer formulations for binary programs
• An effective compact formulation of the max cut problem on sparse graphs
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs

This page was built for publication: A mixed integer model for the sparsest cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2883559)