New algorithms for the intersection problem of submodular systems

DOI10.1007/BF03167272zbMath0770.90073OpenAlexW2026097612MaRDI QIDQ1202762

Xiaodong Zhang, Satoru Fujishige

Publication date: 14 February 1993

Published in: Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

submodular functionintersection problemshortest augmenting pathssubmodular systemsmaximum common subbasepreflow-push approach

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A fast cost scaling algorithm for submodular flow, Separation of partition inequalities with terminals, Finding a Stable Allocation in Polymatroid Intersection, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Simple push-relabel algorithms for matroids and submodular flows, A push-relabel framework for submodular function minimization and applications to parametric optimization, Minimizing a sum of submodular functions, A capacity scaling algorithm for M-convex submodular flow, A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows, Discrete Convex Functions on Graphs and Their Algorithmic Applications, Submodular function minimization, A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem

Cites Work

• Unnamed Item
• Systems analysis by graphs and matroids. Structural solvability and controllability
• An out-of-kilter method for submodular flows
• Submodular functions and optimization
• Analysis of Preflow Push Algorithms for Maximum Network Flow
• A new approach to the maximum-flow problem
• Use of matroid theory in operations research, circuits and systems theory
• Computing Maximal “Polymatroidal” Network Flows
• ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS