2016/06/27 by Kita, Nanao
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1606.08246
We establish the theory of the Dulmage-Mendelsohn decomposition for b-matchings. The original Dulmage-Mendelsohn decomposition is a classical canonical decomposition of bipartite graphs, which describes the structures of the maximum 1-matchings and the dual optimizers, i.e., the minimum vertex covers. In this paper, we develop analogical properties, and thus obtain the structure of the maximum b-matchings and characterizes the family of b-verifying set.