Computing Maximal “Polymatroidal” Network Flows
From MaRDI portal
Publication:3964296
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
max-flow min-cut theoremconstrained flowsmaximal flow algorithmaugmenting path theoremintegral flow theorempolymatroidal network flowcapacities of sets of arcs
Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)
Related Items
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, 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
