A note on the Frank-Tardos bi-truncation algorithm for crossing- submodular functions

DOI10.1007/BF01585712zbMath0749.90026OpenAlexW1994322738MaRDI QIDQ1184356

Takeshi Naitoh, Satoru Fujishige

Publication date: 28 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

bi-truncation algorithmcrossing-submodular function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (3)

Algorithms for finding a rooted \((k,1)\)-edge-connected orientation ⋮ Tree-compositions and orientations ⋮ A cost-scaling algorithm for \(0-1\) submodular flows

Cites Work

• Generalized polymatroids and submodular flows
• Structures of polyhedra determined by submodular functions on crossing families

This page was built for publication: A note on the Frank-Tardos bi-truncation algorithm for crossing- submodular functions