Technical Report CS0093

Title: Some Matching Problems
Authors: Alon Itai and Michael Rodeh
Abstract: In certain applications it is required to find in a bipartite graph a perfect matching which satisfies some additional properties. For one such type of restrictions the problem is proven to be NP-complete. If for a given subset of edges no more than ~ edges may be included in the matching then an O(ne) algorithm is suggested. Finally, an efficient algorithm to find all perfect matchings 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1977
To the main CS technical reports page

Computer science department, Technion