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

DOI10.1016/J.APM.2011.04.027zbMATH Open1228.90016OpenAlexW2049971620MaRDI QIDQ651729FDOQ651729

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

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

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)

Cites Work

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

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)