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

DOI10.1016/J.DISC.2011.05.025MaRDI QIDQ2275455zbMATH OpenOpenAlexFDO

Authors 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

maximum integer multiflowmin-max equalityminimum multicut

Mathematics Subject Classification ID

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

Recommendations

• When the cut condition is enough, a complete characterization for multiflow problems in series-parallel networks
• Flow-cut gaps for integer and fractional multiflows
• Flow-cut gaps for integer and fractional multiflows
• Minimal multicut and maximal integer multiflow: a survey
• Trader multiflow and box-TDI systems in series-parallel graphs

Cites work

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

Cited in

(7)

• Flow-cut gaps for integer and fractional multiflows
• The Schrijver system of the flow cone in series-parallel graphs
• Trader multiflow and box-TDI systems in series-parallel graphs
• Box-total dual integrality and edge-connectivity
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• When the cut condition is enough, a complete characterization for multiflow problems in series-parallel networks
• Flow-cut gaps for integer and fractional multiflows

This page was built for publication: Max-multiflow/min-multicut for G+H series-parallel

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