A generalization of max flow—min cut

DOI10.1007/BF01580250zbMath0357.90068MaRDI QIDQ4133435

Alan J. Hoffman

Publication date: 1974

Published in: Mathematical Programming (Search for Journal in Brave)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (52)

Polyhedral proof methods in combinatorial optimization ⋮ On box totally dual integral polyhedra ⋮ Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation ⋮ Separation, dimension, and facet algorithms for node flow polyhedra ⋮ Solving a capacitated hub location problem ⋮ A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\) ⋮ Switchdec polyhedra ⋮ Generalized polymatroids and submodular flows ⋮ Intersecting restrictions in clutters ⋮ A strongly polynomial algorithm for the uniform balanced network flow problem ⋮ Polyhedral Combinatorics in Combinatorial Optimization ⋮ On Packing Dijoins in Digraphs and Weighted Digraphs ⋮ Decomposition of probability marginals for security games in abstract networks ⋮ Total dual integrality implies local strong unimodularity ⋮ On total dual integrality ⋮ Rerouting Flows when Links Fail ⋮ Unnamed Item ⋮ Total dual integrality and b-matchings ⋮ The max-flow min-cut property and \(\pm 1\)-resistant sets ⋮ Protection of flows under targeted attacks ⋮ An analytical comparison of different formulations of the travelling salesman problem ⋮ On a composition of independence systems by circuit identification ⋮ A Primal-Dual Algorithm for Weighted Abstract Cut Packing ⋮ Cuboids, a class of clutters ⋮ Proving total dual integrality with cross-free families—A general framework ⋮ Circuits in graphs embedded on the torus ⋮ Abstract flows over time: a first step towards solving dynamic packing problems ⋮ Unnamed Item ⋮ On switching paths polyhedra ⋮ A min-max relation for stable sets in graphs with no odd-\(K_ 4\) ⋮ On partitions of a partially ordered set ⋮ Flows on measurable spaces ⋮ A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations ⋮ Connected and alternating vectors: Polyhedra and algorithms ⋮ Matchings and covers in hypergraphs ⋮ On superperfection of edge intersection graphs of paths ⋮ Integral infeasibility and testing total dual integrality ⋮ A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors ⋮ On totally dual integral systems ⋮ Efficient algorithms for abstract flow with partial switching ⋮ The multi-commodity one-to-one pickup-and-delivery traveling salesman problem ⋮ Operations that preserve total dual integrality ⋮ Extending Greene's theorem to directed graphs ⋮ Recent trends in combinatorial optimization ⋮ A Minimal Totally Dual Integral Defining System for the b-Matching Polyhedron ⋮ Nowhere-zero flows in random graphs ⋮ Total weak unimodularity: Testing and applications ⋮ Abstract network flow with intermediate storage for evacuation planning ⋮ Path-closed sets ⋮ Algorithms and complexity analysis for some flow problems ⋮ On the interval chromatic number of proper interval graphs ⋮ An integer analogue of Carathéodory's theorem

Cites Work

• Maximal Flow Through a Network
• Unnamed Item
• Unnamed Item

This page was built for publication: A generalization of max flow—min cut