Fast Algorithms for Bipartite Network Flow

DOI10.1137/0216020MaRDI QIDQ3754450zbMATH OpenOpenAlexFDO

Authors Dan Gusfield, Chip Martel, 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 graphmaximum flowmaximum subgraph densitymultiprocessor schedulingrelease times and deadlinesupper bound for the complexityweighted subgraph density

Mathematics Subject Classification ID

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

Recommendations

• Improved Algorithms for Bipartite Network Flow
• scientific article; zbMATH DE number 177817
• scientific article; zbMATH DE number 4104675
• Maximum flows in bipartite dynamic networks
• The maximum flows in bipartite dynamic networks. The static approach

Cited in

(26)

• 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
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• Reshipments and overshipments in transportation problems with minimax objective
• A fast bipartite network flow algorithm for selective assembly
• A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources
• Network flow and 2-satisfiability
• Scheduling jobs to minimize total cost
• Bounds on maximum concurrent flow in random bipartite graphs
• A new-old algorithm for minimum-cut and maximum-flow in closure graphs.
• The cost scaling algorithm for bipartite networks
• Polymatroidal flow network models with multiple sinks
• scientific article; zbMATH DE number 4104675 (Why is no real title available?)
• scientific article; zbMATH DE number 176474 (Why is no real title available?)
• A fast algorithm for bounded generalized processing networks
• Improved Algorithms for Bipartite Network Flow
• The maximum flows in bipartite dynamic networks. The static approach
• Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs
• Maximum flows in bipartite dynamic networks
• Wave algorithm for maximum flow in bipartite networks
• Solving Maximum Flow Problems on Real World Bipartite Graphs
• Parallel output-sensitive algorithms for combinatorial and linear algebra problems
• The subset assignment problem for data placement in caches
• Baseball playoff eliminations: An application of linear programming. Erratum
• Using combinatorial optimization in model-based trimmed clustering with cardinality constraints

This page was built for publication: Fast Algorithms for Bipartite Network Flow

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