Paper Info
Title
Matchings in Node-Weighted Convex Bipartite Graphs
Abstract
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.
Year
DOI
Venue
2008
10.1287/ijoc.1070.0232
INFORMS Journal on Computing
Keywords
Field
DocType
maximum matchings,release time,linear time algorithm,bipartite graph,j. s. yeomans,convex bipartite graph,maximum matching,node-weighted convex bipartite graph,x-perfect matching,unweighted case,node-weighted convex bipartite graphs,scheduling,graphs,algorithms,matching
Discrete mathematics,Complete bipartite graph,Mathematical optimization,Combinatorics,Convex bipartite graph,Bipartite graph,Hopcroft–Karp algorithm,Matching (graph theory),Assignment problem,3-dimensional matching,Blossom algorithm,Mathematics
Journal
Volume
Issue
ISSN
20
2
1091-9856
Citations 
PageRank 
References 
8
0.59
6
Authors
1
Name
Order
Citations
PageRank
Irit Katriel117613.72