Search Algorithms for a System of Different Representatives of Subsets of a Finite Set

  • Dmitri Terzi State University of Moldova, Chisinau Moldova
Keywords: systems of different representatives, Hall's theorem, algorithmization, combinatorial optimization, transport-type problems


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


Attaway Stormy. (2019). MATLAB A Practical Introduction to Programming and Problem Solving, Elsevier, Butterworth-Heinemann, Oxford-Camdridge.
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.
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
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.