A strongly polynomial algorithm for the minimum maximum flow degree problem

DOI10.1016/J.ORL.2022.12.004MaRDI QIDQ6161285zbMATH OpenOpenAlexFDO

Authors Manoel Campêlo, Jhonata A. S. Matias

Publication date 27 June 2023

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2022.12.004

zbMATH Keywords

linear programmingnetwork flowflow coloring problemminimum maximum flow degree problem

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Mixed integer programming (90C11)

Recommendations

• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• scientific article; zbMATH DE number 4204092
• A strongly polynomial algorithm for generalized flow maximization
• A strongly polynomial algorithm for generalized flow maximization
• Strongly polynomial dual simplex methods for the maximum flow problem

Cites work

• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• An application of simultaneous diophantine approximation in combinatorial optimization
• Network flows. Theory, algorithms, and applications.
• On the complexity of bandwidth allocation in radio networks
• On the complexity of the flow coloring problem

Cited in

(5)

• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
• A strongly polynomial algorithm for generalized flow maximization
• Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
• scientific article; zbMATH DE number 871948 (Why is no real title available?)
• scientific article; zbMATH DE number 6402605 (Why is no real title available?)

This page was built for publication: A strongly polynomial algorithm for the minimum maximum flow degree problem

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