| TR#: | CS0093 |
| Class: | CS |
| Title: | Some Matching Problems |
| Authors: | Alon Itai and Michael Rodeh |
| CS0093.pdf | |
| 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. |
| Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1977/CS/CS0093), 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