Improved Algorithms for Bipartite Network Flow
From MaRDI portal
Publication:4312415
DOI10.1137/S0097539791199334zbMath0840.90063OpenAlexW2056991815MaRDI QIDQ4312415
Ravindra K. Ahuja, James B. Orlin, Robert Endre Tarjan, Clifford Stein
Publication date: 4 July 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539791199334
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)
Related Items
Efficient algorithms for robustness in resource allocation and scheduling problems, A Fluid Model for One-Sided Bipartite Matching Queues with Match-Dependent Rewards, A space-efficient simulation algorithm on probabilistic automata, On a generalization of Nemhauser and Trotter's local optimization theorem, A fast algorithm for the minimax flow problem with 0/1 weights, An efficient cost scaling algorithm for the assignment problem, Geometric algorithms for the minimum cost assignment problem, Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities, On coresets for fair clustering in metric and Euclidean spaces and their applications, Scheduling jobs with sizes and delivery times on identical parallel batch machines, Algorithms for distributing telecommunication traffic on a multiple-ring SONET-based network., Restricted assignment scheduling with resource constraints, Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach, Preemptive scheduling on uniform parallel machines with controllable job processing times, An adaptive time slot assignment algorithm for variable bandwidth switching systems, Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs, The partition bargaining problem, Dynamic evolution of economically preferred facilities, Reformulating linear programs with transportation constraints-With applications to workforce scheduling, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches, Using combinatorial optimization in model-based trimmed clustering with cardinality constraints, Lower bounds for the earliness-tardiness scheduling problem on parallel machines with distinct due dates, Two level hierarchical time minimizing transportation problem, Level of repair analysis and minimum cost homomorphisms of graphs, Structural and algorithmic properties for parametric minimum cuts, The subset assignment problem for data placement in caches, Max-min sum minimization transportation problem, Approximability issues for unconstrained and constrained maximization of half-product related functions, A faster polynomial algorithm for the unbalanced Hitchcock transportation problem, Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines, A strongly polynomial algorithm for the transportation problem, Geometric quadrisection in linear time, with application to VLSI placement, Parameterized algorithms and complexity for the traveling purchaser problem and its variants, Network reinforcement, A technique for speeding up the solution of the Lagrangean dual, A note on optimal covering augmentation for graphic polymatroids.
