|
|||||
|
|
A linear time algorithm for maximum matchings in convex, bipartite graphs |
|
| Authors: | G Steiner JS Yeomans |
| Affiliation: | Management Science and Information Systems Area Faculty of Business, McMaster University, Hamilton, Ontario, Canada, L8S 4M4 Management Science Area, Faculty of Administrative Studies, York University, North York, Ontario, Canada, M3J 1P3 |
| Abstract: | The problem of determining the maximum matching in a convex bipartite graph, G = (V1, V2, E), is considered. It is shown that by using the appropriate data structures, the maximum matching problem can be efficiently transformed into an off-line minimum problem. Since the off-line minimum problem has been shown to be linear, the maximum matching in a convex bipartite graph can be determined in O(|V1|) time. |
| Keywords: | Maximum matchings Convex bipartite graphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |