On the minimum \(s-t\) cut problem with budget constraints

DOI10.1007/s10107-023-01987-9MaRDI QIDQ6120941

Hassene Aissi, Ali Ridha Mahjoub

Publication date: 21 February 2024

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

zbMATH Keywords

linear programmingbudget constraintsminimum \(s-t\) cut problem

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• New approaches to multi-objective optimization
• On a multicriteria shortest path problem
• A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem
• How easy is local search?
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts
• The constrained minimum weighted sum of job completion times problem
• Multicriteria global minimum cuts
• Simple Local Search Problems that are Hard to Solve
• On the structure of all minimum cuts in a network and applications
• Hardness and approximation for network flow interdiction
• Properties of vertex packing and independence system polyhedra
• The constrained minimum spanning tree problem
• Suboptimal cuts: Their enumeration, weight and number
• Multicriteria Optimization
• Algorithms – ESA 2005

This page was built for publication: On the minimum \(s-t\) cut problem with budget constraints