Fast Algorithms for Bipartite Network Flow

DOI10.1137/0216020zbMATH Open0617.90082OpenAlexW2006254094MaRDI QIDQ3754450FDOQ3754450

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

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

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)

Cited In (25)

• Maximum flows in bipartite dynamic networks
• A new-old algorithm for minimum-cut and maximum-flow in closure graphs.
• Scheduling unit-time jobs on processors with different capabilities
• Bounds on maximum concurrent flow in random bipartite graphs
• On the efficiency of maximum-flow algorithms on networks with small integer capacities
• A fast algorithm for bounded generalized processing networks
• The subset assignment problem for data placement in caches
• Title not available (Why is that?)
• Title not available (Why is that?)
• Wave algorithm for maximum flow in bipartite networks
• The maximum flows in bipartite dynamic networks. The static approach
• Network flow and 2-satisfiability
• Improved Algorithms for Bipartite Network Flow
• Solving Maximum Flow Problems on Real World Bipartite Graphs
• Scheduling jobs to minimize total cost
• 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
• The cost scaling algorithm for bipartite networks
• Parallel output-sensitive algorithms for combinatorial and linear algebra problems
• A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources
• Using combinatorial optimization in model-based trimmed clustering with cardinality constraints
• A parametric maximum flow algorithm for bipartite graphs with applications
• Baseball playoff eliminations: An application of linear programming. Erratum
• Polymatroidal flow network models with multiple sinks

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)