About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
Some Matching Problems for Bipartite Graphs
Abstract
Certam apphcatlons require finding a perfect matching in a bipartite graph that satisfies some additional properties For one such type of restncUon the problem is proven to be NP-complete. If for a single subset of edges no more than r edges may be included m the matching then an O(ne) algorithm is given An efficient algorithm for finding all perfect matchmgs is presented It requires O(e) time per matching and a total of O(e) space This algorithm may be used to calculate the permanent of a matrix Finally, the algorithm ts generahzed to find all maximum matchmgs. © 1978, ACM. All rights reserved.