Computing Maximal “Polymatroidal” Network Flows

DOI10.1287/MOOR.7.3.334zbMath0498.90029OpenAlexW2124531440MaRDI QIDQ3964296

Charles U. Martel, Eugene L. Lawler

Publication date: 1982

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.7.3.334

zbMATH Keywords

max-flow min-cut theoremconstrained flowsmaximal flow algorithmaugmenting path theoremintegral flow theorempolymatroidal network flowcapacities of sets of arcs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items (29)

Maximal dynamic polymatroid flows and applications ⋮ A fast cost scaling algorithm for submodular flow ⋮ An out-of-kilter method for submodular flows ⋮ Separation, dimension, and facet algorithms for node flow polyhedra ⋮ Countable Menger's theorem with finitary matroid constraints on the ingoing edges ⋮ Polyhedral Clinching Auctions for Two-Sided Markets ⋮ Generalized polymatroids and submodular flows ⋮ Directed submodularity, ditroids and directed submodular flows ⋮ An application of submodular flows ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ Simple push-relabel algorithms for matroids and submodular flows ⋮ A note on polylinking flow networks ⋮ Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives ⋮ Minimization on submodular flows ⋮ A competitive two-agent scheduling problem on parallel machines with release dates and preemption ⋮ Two algorithms for maximizing a separable concave function over a polymatroid feasible region ⋮ Proving total dual integrality with cross-free families—A general framework ⋮ Graph cuts with interacting edge weights: examples, approximations, and algorithms ⋮ New algorithms for the intersection problem of submodular systems ⋮ Structures of polyhedra determined by submodular functions on crossing families ⋮ Polymatroidal flows with lower bounds ⋮ A characterization of network representable polymatroids ⋮ Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications ⋮ Ex ante and ex post envy-freeness on polytope resources ⋮ A node-capacitated Okamura-Seymour theorem ⋮ Multicommodity flows and cuts in polymatroidal networks ⋮ A combinatorial algorithm minimizing submodular functions in strongly polynomial time. ⋮ Testing membership in matroid polyhedra ⋮ Finding feasible vectors of Edmonds-Giles polyhedra

This page was built for publication: Computing Maximal “Polymatroidal” Network Flows