Single commodity-flow algorithms for lifts of graphic and cographic matroids

DOI10.1137/130937603MaRDI QIDQ2820860zbMATH OpenOpenAlexFDO

Authors Bertrand Guenin, Leanne Stuive

Publication date 9 September 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d2e742f5caef01033f7969a1ed13bce41d7f3c69

zbMATH Keywords

ellipsoid methodeven cut matroideven cycle matroidLehman's theoremmax cutmulti-commodity flowsset covering polyhedraweakly bipartite graphs

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Signed and weighted graphs (05C22) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Minimax problems in mathematical programming (90C47)

Recommendations

• Single Commodity-Flow Algorithms for Lifts of Graphic and Co-graphic Matroids
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
• Recognizing max-flow min-cut path matrices
• scientific article; zbMATH DE number 4212067
• A survey on flows in graphs and matroids

Cites work

• A characterization of weakly bipartite graphs
• A short proof of Guenin's characterization of weakly bipartite graphs
• A Solution of the Shannon Switching Game
• Biased graphs. I: Bias, balance, and gains
• Bottleneck extrema
• Combinatorial designs and related systems
• Combinatorial optimization. Packing and covering
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 3750980 (Why is no real title available?)
• scientific article; zbMATH DE number 16723 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• scientific article; zbMATH DE number 3049937 (Why is no real title available?)
• Integral Polyhedra Related to Even-Cycle and Even-Cut Matroids
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
• Maximal Flow Through a Network
• Packing odd circuits in Eulerian graphs
• Single Commodity-Flow Algorithms for Lifts of Graphic and Co-graphic Matroids
• The extremal length of a network
• The Forbidden Minors of Binary Clutters
• The Graph Minor Algorithm with Parity Conditions
• The matroids with the max-flow min-cut property
• Towards a matroid-minor structure theory

Cited in

(2)

• Single Commodity-Flow Algorithms for Lifts of Graphic and Co-graphic Matroids
• Lifting, superadditivity, mixed integer rounding and single node flow sets revisited

This page was built for publication: Single commodity-flow algorithms for lifts of graphic and cographic matroids

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