Fast Algorithms for Bipartite Network Flow

DOI10.1137/0216020MaRDI QIDQ3754450zbMATHOpenAlexFDO

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

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

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

(25)

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

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)