| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949480 | Discrete Applied Mathematics | 2017 | 9 Pages |
Abstract
In this paper, we further investigate the structure of square-free 2-matchings in bipartite graphs and present new decomposition theorems. These theorems serve as analogues of the Dulmage-Mendelsohn decomposition for matchings in bipartite graphs and the Edmonds-Gallai decomposition for matchings in nonbipartite graphs. We exhibit two canonical minimizers for the set function in the min-max formula, and a characterization of the maximum square-free 2-matchings with the aid of these canonical minimizers.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kenjiro Takazawa,