Max-multiflow/min-multicut for G+H series-parallel

DOI10.1016/j.disc.2011.05.025zbMath1223.05105OpenAlexW2114145571MaRDI QIDQ2275455

Denis Cornaz

Publication date: 9 August 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.05.025

zbMATH Keywords

minimum multicutmin-max equalitymaximum integer multiflow

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) Flows in graphs (05C21)

Related Items

Trader multiflow and box-TDI systems in series-parallel graphs, Box-total dual integrality and edge-connectivity, The Schrijver system of the flow cone in series-parallel graphs, An Approximation Algorithm for Fully Planar Edge-Disjoint Paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the planar integer two-flow problem
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• Facets of the clique partitioning polytope
• Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
• Matroids and multicommodity flows
• The matroids with the max-flow min-cut property
• Integer plane multiflows with a mixed number of demands
• Models and algorithms for the 2-dimensional cell suppression problem in statistical disclosure control
• Finding edge-disjoint paths in partial \(k\)-trees
• On the complexity of the disjoint paths problem
• A logical approach to multicut problems
• Topology of series-parallel networks
• Colouring series-parallel graphs
• Multiflow Feasibility: An Annotated Tableau
• On Integer Multiflow Maximization
• The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
• On the cut polytope
• A Note on Clique-Web Facets for Multicut Polytopes
• Geometry of cuts and metrics
• The edge-disjoint paths problem is NP-complete for series-parallel graphs