A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows

DOI10.1080/02331939608844244zbMath0868.90094OpenAlexW2065767781MaRDI QIDQ2785397

Satoru Fujishige, Xiaodong Zhang

Publication date: 18 August 1997

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331939608844244

zbMATH Keywords

submodular flowminimum-cost flowsindependent assignmentpush/relabelsubmodular intersection problem

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Simple push-relabel algorithms for matroids and submodular flows

Cites Work

• Unnamed Item
• Unnamed Item
• An application of simultaneous diophantine approximation in combinatorial optimization
• How to make a digraph strongly connected
• Submodular functions and optimization
• Negative circuits for flows and submodular flows
• New algorithms for the intersection problem of submodular systems
• A polynomial cycle canceling algorithm for submodular flows
• Finding Minimum-Cost Circulations by Successive Approximation
• A Primal-Dual Algorithm for Submodular Flows
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• A Minimax Theorem for Directed Graphs
• An Algorithm for Submodular Functions on Graphs
• Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization