SIAM Journal on Computing · 1987 · 58 citations · 19 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationCombinatorial OptimizationComputational ComplexityGraph AlgorithmsGraph TheoryNetwork Flow AlgorithmsNetwork FlowsBipartite NetworksComputational Complexity Of Graph AlgorithmsLower BoundsNetwork Flow Problems
We discuss network flow in a bipartite graph G with node sets S and T. We show that Karzanov’s algorithm runs in time $O(|S|^2 |T|)$ on G, and that the MPM algorithm can be modified to run in the same bound. For the common case that the degree of each node in T is bounded by a constant, we show that a modified version of the MPM algorithm runs in time $O(|S|^3 + |S||T|)$ on G. The importance of these results comes from the common occurrence of problems that can be modeled and solved using network flow on bipartite graphs where $|S| \ll |T|$. In many applications involving bounded degree on the nodes in T, $|T| = \theta (|S|^2 )$, and our results reduce the best bounds on bipartite flow from $O(|S|^6 )$ to $O(|S|^3 )$. We use our results on bipartite flow to obtain the fastest known bounds on several combinatorial problems, and mention several additional problems involving bipartite flow where $|S|$ is much smaller than $|T|$.
19
Self-adjusting binary search trees
Daniel D. Sleator, Robert E. Tarjan · Journal of the ACM · 1985 · 1.2K citations · Full text
Scheduling with Deadlines and Loss Functions
Robert McNaughton · Management Science · 1959 · 846 citations