Packing and covering with integral feasible flows in integral supply-demand networks

DOI10.1007/BF02592074zbMath0646.90033OpenAlexW2025792637MaRDI QIDQ3790920

O. M.-C. Marcotte, Robert E. Bixby, Leslie E. jun. Trotter

Publication date: 1987

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

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

zbMATH Keywords

decompositionpolynomial-time algorithmpacking and coveringtotally unimodular systemsintegral feasible flowsintegral supply-demand network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Combinatorial aspects of packing and covering (05B40)

Related Items (4)

Strength of a graph and packing of trees and branchings ⋮ On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond ⋮ An application of simultaneous diophantine approximation in combinatorial optimization ⋮ Integral packing of trees and branchings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An integer analogue of Carathéodory's theorem
• Decomposition of regular matroids
• The ellipsoid method and its consequences in combinatorial optimization
• Blocking pairs of polyhedra arising from network flows
• On a Class of Capacitated Transportation Problems
• Fractional covers for forests and matchings
• Integer Rounding for Polymatroid and Branching Optimization Problems
• Optimal attack and reinforcement of a network
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Network Flows, Minimum Coverings, and the Four-Color Conjectures
• Minimum partition of a matroid into independent subsets

This page was built for publication: Packing and covering with integral feasible flows in integral supply-demand networks