Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem
From MaRDI portal
Publication:3186492
DOI10.1007/978-3-319-33461-5_6zbMath1419.90110OpenAlexW2478657554MaRDI QIDQ3186492
Francisco Barahona, Mourad Baïou
Publication date: 10 August 2016
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-33461-5_6
Related Items
Cites Work
- 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
- 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
- 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
