A strongly polynomial cut canceling algorithm for the submodular flow problem

DOI10.1007/3-540-48777-8_20MaRDI QIDQ4263717zbMATH OpenFDO

Authors Satoru Iwata, S. Thomas McCormick, Maiko Shigeno

Publication date 22 September 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48777-8_20

zbMATH Keywords

cut canceling algorithmstrongly polynomial running timesubmodular max flow problem

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Recommendations

• A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow
• scientific article; zbMATH DE number 1263281
• A polynomial cycle canceling algorithm for submodular flows
• scientific article; zbMATH DE number 1303553
• A faster capacity scaling algorithm for minimum cost submodular flow

Cited in

(8)

• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A capacity scaling algorithm for M-convex submodular flow
• A polynomial cycle canceling algorithm for submodular flows
• Fast cycle canceling algorithms for minimum cost submodular flow
• A fast cost scaling algorithm for submodular flow
• A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems
• scientific article; zbMATH DE number 1263281 (Why is no real title available?)
• A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow

This page was built for publication: A strongly polynomial cut canceling algorithm for the submodular flow problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4263717)