Proving total dual integrality with cross-free families—A general framework
From MaRDI portal
Publication:3313630
DOI10.1007/BF02591726zbMath0531.90076MaRDI QIDQ3313630
Publication date: 1984
Published in: Mathematical Programming (Search for Journal in Brave)
total dual integralitytotal unimodularitypolymatroidal network flowscross-freekernel systemsubmodular, lattice polyhedra
Related Items
On box totally dual integral polyhedra, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, An exact algorithm for the preemptive single machine scheduling of equal-length jobs, Generalized polymatroids and submodular flows, An application of submodular flows, Characterizing and recognizing generalized polymatroids, A system of linear inequalities with a submodular function on \(\{0,\pm 1\}\) vectors, Operations that preserve total dual integrality, Packing and covering of crossing families of cuts, An integer analogue of Carathéodory's theorem
Cites Work
- Short proofs on the matching polyhedron
- The ellipsoid method and its consequences in combinatorial optimization
- Maximal Flow Through a Network
- Polyhedra related to a lattice
- Optimum matching forests I: Special weights
- Optimum matching forests II: General weights
- Optimum matching forests III: Facets of matching forest polyhedra
- Min-max Relations for Directed Graphs
- Minimization of Some Nonlinear Functions over Polymatroidal Network Flows
- Computing Maximal “Polymatroidal” Network Flows
- A generalization of max flow—min cut
- ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
- A Minimax Theorem for Directed Graphs
- An Algorithm for Submodular Functions on Graphs
- Packing rooted directed cuts in a weighted directed graph
- Lectures on matroids
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
