Fast Algorithms for Bipartite Network Flow

DOI10.1137/0216020zbMATH Open0617.90082OpenAlexW2006254094MaRDI QIDQ3754450FDOQ3754450

Chip 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 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 (19)

• A new-old algorithm for minimum-cut and maximum-flow in closure graphs.
• Scheduling unit-time jobs on processors with different capabilities
• 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?)
• 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
• 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

   Recommendations

• Improved Algorithms for Bipartite Network Flow 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Maximum flows in bipartite dynamic networks 👍 👎
• Title not available (Why is that?) 👍 👎

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)