Czygrinow, A., Hanćkowiak, M., Szymańska, E. and Wawrzyniak, W. (2016) On the Distributed Complexity of the Semi-Matching Problem. Journal of Computer and System Sciences, 82, 1251-1267.
https://doi.org/10.1016/j.jcss.2016.05.001

has been cited by the following article:

• TITLE: Perfect 1-k Matchings of Bipartite Graphs

  AUTHORS: Wenduan Dai, Yan Liu, Yanfang Wu

  KEYWORDS: Bipartite Graph, Semi-Matching, Perfect 1-k Matching, k-Elementary Graph

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.14 No.4, September 25, 2024

  ABSTRACT: Let k be a positive integer and G a bipartite graph with bipartition ( X,Y ) . A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−d vertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.