An \(O(IVI^3)\) algorithm for finding maximum flows in networks
From MaRDI portal
Publication:1251587
DOI10.1016/0020-0190(78)90016-9zbMath0391.90041OpenAlexW2081013866WikidataQ55934324 ScholiaQ55934324MaRDI QIDQ1251587
S. N. Maheshwari, M. Pramodh Kumar, Vishv Mohan Malhotra
Publication date: 1978
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(78)90016-9
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Graph theory (05C99)
Related Items
Length-bounded cuts: proper interval graphs and structural parameters, A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing, Local optima topology for the \(k\)-coloring problem, Unimodular functions, Scheduling jobs to minimize total cost, Solving matching problems with linear programming, A decomposition algorithm for multi-terminal network flows, Multi-terminal maximum flows in node-capacitated networks, Sandpile models and lattices: a comprehensive survey, A generalization of the scaling max-flow algorithm, Quick max-flow algorithm, Exploiting locality in LT-RAM computations, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, On the efficiency of maximum-flow algorithms on networks with small integer capacities, Collision-free routing problem with restricted L-path, Simplifications and speedups of the pseudoflow algorithm, A new polynomial-time algorithm for the maximum weighted (?(G) ? 1)-coloring problem in comparability graphs, Scheduling unit-time jobs on processors with different capabilities, A parametric maximum flow algorithm for bipartite graphs with applications, Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach, Algebraic flows in regular matroids, Cutoff stability under distributional constraints with an application to summer internship matching, Methods for the graph realization problem, An \(O(EV\log^2V)\) algorithm for the maximal flow problem, The maximum flow problem of uncertain network, An \(O(V^{5/3}E^{2/3})\) algorithm for the maximal flow problem, On the theoretical efficiency of various network flow algorithms, Multiterminal global routing: A deterministic approximation scheme, Unnamed Item, On complexity, representation and approximation of integral multicommodity flows, BDDs -- design, analysis, complexity, and applications., The translation square map and approximate congruence, Deciding bisimilarity and similarity for probabilistic processes., Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs, An optimal algorithm for \(2 \times{} n\) bottleneck transportation problems, On the computational behavior of a polynomial-time network flow algorithm, A new Karzanov-type \(O(n^ 3)\) max-flow algorithm, AO(nm log(U/n)) time maximum flow algorithm, Minimizing mean weighted execution time loss on identical and uniform processors, Executability of scenarios in Petri nets, Towards equitable distribution via proportional equity constraints, Computing the throughput of a network with dedicated lines, A parallel algorithm for finding a blocking flow in an acyclic network, A heuristic for blocking flow algorithms, Computational investigations of maximum flow algorithms, Finding the most vital arcs in a network, Source reversal and chip firing on graphs, Evaluating Reliability of Stochastic Flow Networks, A data structure for dynamic trees, Stability of metabolic networks via linear-in-flux-expressions, Decomposition algorithms for locating minimal cuts in a network, Recent trends in combinatorial optimization, A simple version of Karzanov's blocking flow algorithm, An algorithmic study of the maximum flow problem: A comparative statistical analysis, Coding distributive lattices with Edge Firing Games., Minimum-weight vertex cover problem for two-class resource connection graphs, A decomposition algorithm for linear relaxation of the weightedr-covering problem, The maximum flow problem: A max-preflow approach
Cites Work
