Integral decomposition in polyhedra

DOI10.1007/BF02591770zbMath0504.90051OpenAlexW2065925866MaRDI QIDQ4740329

Colin J. H. McDiarmid

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1007/bf02591770

zbMATH Keywords

directed graphnetwork flowsbranchingsconvex polyhedratotally unimodular matrixintegral polymatroidstrongly-base-orderable matroidsweak integral decomposition

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Combinatorial aspects of packing and covering (05B40) Polytopes and polyhedra (52Bxx)

Related Items

A decomposition property of polyhedra ⋮ Edge-Disjoint Branchings in Temporal Graphs ⋮ A generalization of Robacker's theorem ⋮ Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ Edge-disjoint branchings in temporal digraphs ⋮ Polyhedra with the integer Carathéodory property

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Blocking pairs of polyhedra arising from network flows
• Blocking, antiblocking, and pairs of matroids and polymatroids
• The edge-coloring of complete hypergraphs. I
• Integer Rounding for Polymatroid and Branching Optimization Problems
• On some characterisations of totally unimodular matrices
• Finite checkability for integer rounding properties in combinatorial programming problems
• A polynomial algorithm for integer programming covering problems satisfying the integer round-up property
• The Induction of Matroids by Graphs^†
• Rado's theorem for polymatroids
• Network Flows, Minimum Coverings, and the Four-Color Conjectures
• Transversal matroid intersections and related packings
• On the Complexity of Timetable and Multicommodity Flow Problems
• Disjoint Common Transversals and Exchange Structures
• Packing rooted directed cuts in a weighted directed graph
• Induced Matroids
• Blocking and anti-blocking pairs of polyhedra