Single Commodity-Flow Algorithms for Lifts of Graphic and CoGraphic Matroids

DOI10.1137/130937603zbMath1344.05040OpenAlexW2517383840MaRDI QIDQ2820860

Guenin, Bertrand, 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

even cycle matroidmulti-commodity flowsellipsoid methodset covering polyhedraLehman's theoremweakly bipartite graphsmax cuteven cut matroid

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Biased graphs. I: Bias, balance, and gains
• The extremal length of a network
• Geometric algorithms and combinatorial optimization
• The matroids with the max-flow min-cut property
• Packing odd circuits in Eulerian graphs
• A characterization of weakly bipartite graphs
• A short proof of Guenin's characterization of weakly bipartite graphs
• Combinatorial designs and related systems
• Combinatorial Optimization
• Maximal Flow Through a Network
• The Forbidden Minors of Binary Clutters
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
• Single Commodity-Flow Algorithms for Lifts of Graphic and Co-graphic Matroids
• The Graph Minor Algorithm with Parity Conditions
• A Solution of the Shannon Switching Game
• Bottleneck extrema
• Integral Polyhedra Related to Even-Cycle and Even-Cut Matroids

This page was built for publication: Single Commodity-Flow Algorithms for Lifts of Graphic and CoGraphic Matroids