Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem

DOI10.1007/s10107-017-1227-3zbMath1406.90102OpenAlexW2794098650MaRDI QIDQ1800990

Mourad Baïou, Francisco Barahona

Publication date: 26 October 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-017-1227-3

zbMATH Keywords

planar graphsmax-cutsparsest cutmaximum concurrent flow

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• On cuts and matchings in planar graphs
• A framework for solving VLSI graph layout problems
• Sparsest cuts and bottlenecks in graphs
• Multicommodity flows in planar graphs
• Matroids and multicommodity flows
• An approximate max-flow min-cut relation for undirected multicommodity flow, with applications
• Improved bounds on the max-flow min-cut ratio for multicommodity flows
• Polynomiality of sparsest cuts with fixed number of sources
• A class of inverse dominant problems under weighted \(l_{\infty }\) norm and an improved complexity bound for Radzik's algorithm
• Über eine Eigenschaft der ebenen Komplexe
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Maximal Flow Through a Network
• The traveling salesman problem in graphs with 3-edge cutsets
• A Separator Theorem for Planar Graphs
• On Odd Cuts and Plane Multicommodity Flows
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Matching, Euler tours and the Chinese postman
• Excluded minors, network decomposition, and multicommodity flow
• Finding minimum-quotient cuts in planar graphs
• Euclidean distortion and the sparsest cut
• A New Min‐Cut Max‐Flow Ratio for Multicommodity Flows
• Optimization and Recognition for K 5-minor Free Graphs in Linear Time
• Sparsest cut on bounded treewidth graphs
• On Nonlinear Fractional Programming
• Multi-Commodity Network Flows
• Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem