An O(mn (nU)) time algorithm to solve the feasibility problem

DOI10.1016/J.APM.2011.04.027MaRDI QIDQ651729zbMATH OpenOpenAlexFDO

Authors Mehdi Ghiyasvand

Publication date 18 December 2011

Published in Applied Mathematical Modelling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apm.2011.04.027

zbMATH Keywords

network flowsthe infeasibility algorithmthe infeasibility problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic network models in operations research (90B10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A new algorithm for solving the feasibility problem of a network flow
• AO(nm log(U/n)) time maximum flow algorithm
• Improved Time Bounds for the Maximum Flow Problem
• Max flows in \(O(nm)\) time, or better
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n^ 2m) time

Cites work

• scientific article; zbMATH DE number 3156381 (Why is no real title available?)
• scientific article; zbMATH DE number 3227800 (Why is no real title available?)
• A Faster Deterministic Maximum Flow Algorithm
• A data structure for dynamic trees
• A new algorithm for solving the feasibility problem of a network flow
• A new approach for computing a most positive cut using the minimum flow algorithms
• A new approach to the maximum-flow problem
• Beyond the flow decomposition barrier
• Computing maximum mean cuts
• Improved Time Bounds for the Maximum Flow Problem
• Network flows. Theory, algorithms, and applications.
• Online load balancing and network flow
• Scaling algorithms for network problems
• The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm

Cited in

(4)

• Diagnosing Infeasibility in Min-cast Network Flow Problems Part I: Dual Infeasibility
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A discrete EOQ problem is solvable in \(O(\log n)\) time
• A new algorithm for solving the feasibility problem of a network flow

This page was built for publication: An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem

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