Search Algorithms for a System of Different Representatives of Subsets of a Finite Set
Abstract
The paper considers various aspects and approaches regarding the search for a system of differenrt representatives (SDR) of subsets of a finite set. Algorithm 3 has been developed, which is an algorithmization of the search process for SDR on the basis of Hall's theorem on the existence of SDR. Algorithms 1-5 for searching for partial and complete SDRs based on the technology for solving problems of the transport type, in particular, the algorithm associated with the construction of cycles, are given. SDR search algorithms can be used as auxiliary tools for solving combinatorial problems. It is also shown, conversely, that the search for SDR can be considered as a combinatorial optimization problem.
Mathematics Subject Classification – MSC2020: 90-08, 90B06, 90C27
References
Brualdi, R.A. (2009). Introductory Combinatorics, Pearson India Education Service.
Hall, M. (1967). Combinatorial Theory, Blaisdell Publishing Company, Waltham -Toronto-London.
Jukna, S. (2011). Extremal Combinatorics. Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17364-6
Korte, B., & Vygen, J. (2015). Combinatorial optimization Theory and Algorithms, Springer-Verlag Berlin Heidelberg.
Lipski, W. (1982). Kombinatoryka dla programistow, Wydawnictwa naukowo-techiczne Warszawa.
Morris, J. (2023). Combinatorics from https://www.cs.uleth.ca/~morris/Combinatorics.
Rybnikov, K. A. (1985). Introduction to combinatorial analysis, 2nd ed, Moscow, Moscow University Press, (russ.).
Wilson, R. (1972). Introduction to graph theory, Oliver and Boyd Edinburgh.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright for this article is retained by the author(s), with first publication rights granted to the journal.
This is an open-access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/).
