Fast Algorithms for Bipartite Network Flow

DOI10.1137/0216020zbMath0617.90082OpenAlexW2006254094MaRDI QIDQ3754450

Charles U. Martel, Dan Gusfield, David Fernández Baca

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216020

zbMATH Keywords

bipartite graphmultiprocessor schedulingmaximum flowmaximum subgraph densityrelease times and deadlinesupper bound for the complexityweighted subgraph density

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

Scheduling jobs to minimize total cost ⋮ On the efficiency of maximum-flow algorithms on networks with small integer capacities ⋮ Scheduling unit-time jobs on processors with different capabilities ⋮ A parametric maximum flow algorithm for bipartite graphs with applications ⋮ Polymatroidal flow network models with multiple sinks ⋮ On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem ⋮ Reshipments and overshipments in transportation problems with minimax objective ⋮ Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs ⋮ A new?old algorithm for minimum-cut and maximum-flow in closure graphs ⋮ Using combinatorial optimization in model-based trimmed clustering with cardinality constraints ⋮ Parallel output-sensitive algorithms for combinatorial and linear algebra problems ⋮ The subset assignment problem for data placement in caches ⋮ A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources ⋮ Baseball playoff eliminations: An application of linear programming. Erratum