全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

Perfect 1-k Matchings of Bipartite Graphs

DOI: 10.4236/ojdm.2024.144005, PP. 43-53

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

Full-Text   Cite this paper   Add to My Lib

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.

References

[1]  Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer-Verlag, Berlin.
[2]  Lawler, E. (2001) Combinatorial Optimization: Networks and Matroids. Dover Publications, New York.
[3]  Harvey, N.J.A., Ladner, R.E., Lovász, L. and Tamir, T. (2006) Semi-Matchings for Bipartite Graphs and Load Balancing. Journal of Algorithms, 59, 53-78.
https://doi.org/10.1016/j.jalgor.2005.01.003
[4]  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
[5]  Xu, J., Banerjee, S. and Rao, W. (2020) The Existence of Universally Agreed Fairest Semi-Matchings in Any Given Bipartite Graph. Theoretical Computer Science, 818, 83-91.
https://doi.org/10.1016/j.tcs.2018.03.020
[6]  Low, C.P. (2006) An Approximation Algorithm for the Load-Balanced Semi-Matching Problem in Weighted Bipartite Graphs. Information Processing Letters, 100, 154-161.
https://doi.org/10.1016/j.ipl.2006.06.004
[7]  Izumi, H., Watanabe, S. and Watanabe, Y. (2017) Augmenting Trail Theorem for the Maximum 1-2 Matching Problem. Discrete Mathematics, Algorithms and Applications, 9, 1750056.
https://doi.org/10.1142/s1793830917500562
[8]  Lovasz, L. and Plummer, M. (1986) Matching Theory. North-Holland, New York
[9]  Bollobás, B. (1998) Modern Graph Theory. Springer, New York.

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133