On the maximum 2-1 matching
type: Item
instance of: scholarly article
title: On the maximum 2-1 matching
zbMATH Open document ID: 0632.90082
DOI: 10.1007/BF02008368
author: Guoli Ding
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 1987-01-01T00:00:00Z
review text: Given a simple bipartite graph \(G=(X,Y,E)\), \(M\subseteq E\) is called a 2- 1 matching of G if: 1) for all \(x\in X\), either two edges or none in M is incident to x and 2) for all \(y\in Y\), at most one edge in M is incident to y. We describe an efficient algorithm for finding a maximum 2-1 matching in a given bipartite graph. We also formulate and prove a duality theorem for 2-1 matching.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 4029295
zbMATH Keywords: bipartite graph
zbMATH Keywords: 2-1 matching
MaRDI profile type: Publication
cites work: Paths, Trees, and Flowers
cites work: Q3048571
Recommended article: The maximum 1-2 matching problem and two kinds of its variants
Recommended article: Maximum and optimal 1-2 matching problem of the different kind
Recommended article: On optimal matchings
Recommended article: Maximum cardinality 1-restricted simple 2-matchings
Recommended article: Tight bounds on maximal and maximum matchings
Recommended article: Q4474098
Recommended article: Q4729838
Recommended article: Maximum induced matchings close to maximum matchings
Recommended article: On one-sided versus two-sided matching games
Recommended article: On the ratio between the maximum weight of a perfect matching and the maximum weight of a matching
description: scientific article; zbMATH DE number 4029295