Matchings in Node-Weighted Convex Bipartite Graphs

Matchings in convex bipartite graphs correspond to the problem of scheduling unit-length tasks on a single disjunctive resource, given a release time and a deadline for every task. The unweighted case was studied by several authors since Glover first considered the problem in 1967 [Glover, F. 1967. Maximum matching in convex bipartite graphs. Naval Res. Logist. Quart.14 313–316] and until 1996, when Steiner and Yeomans found an algorithm whose running time is linear in the number of tasks [Steiner, G., J. S. Yeomans. 1996. A linear time algorithm for determining maximum matchings in convex, bipartite graphs. Comput. Math. Appl.31(12) 91–96]. We address a weighted variant of this problem. Given a node-weighted convex bipartite graph G=(X, Y, E) (where Y is linearly ordered and the neighborhood of each node of X is an interval of Y), we show that it is possible to find an X-perfect matching of maximum (or minimum) weight in O(|E| + |Y| log |X|) time and O(|X| + |Y|) space. For the case in which only the nodes of Y are weighted and their weights are positive, the algorithm can be used to find a maximum-weight (not necessarily X-perfect) matching.