Abstract
A set of methods for limiting the complete enumeration of the number of combinations \(C_n^k\) for \(1\le k\le n\) is proposed. The proposed methods can be used in combinatorial algorithms for calculating subsets of the original set. They are applicable if the calculation of subsets is carried out using a selection function with certain properties. An example of using an algorithm to calculate the set of minimal sections of a graph is considered. It is shown that these methods can be used to solve a number of different NP-complete problems. The results of numerical experiments are presented.
Supported by V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Grebenuk, G., Nikishov, S.: Blocking of energy and resource supply of target objects in network infrastructures. Control Sci. 4, 52–57 (2016)
Reinhard, D.: Graph Theory. Electronic Edition. Springer-Verlag, Heidelberg (2005) https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 554–565. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04128-0_50
Garey, M., Johnson, D.: Computers and Intractability. W. H. Freeman and Company, United States (1979)
Taylor, M., D’Este, Glen M.: Transport network vulnerability: a method for diagnosis of critical locations in transport infrastructure systems. In: Critical infrastructure: Reliability and vulnerability, pp. 9–30. Springer, Berlin (2007). https://doi.org/10.1007/978-3-540-68056-7_2
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kuprijanov, B.V., Roschin, A. (2023). Limiting the Search in Brute Force Method for Subsets Detection. In: Olenev, N., Evtushenko, Y., Jaćimović, M., Khachay, M., Malkova, V. (eds) Optimization and Applications. OPTIMA 2023. Lecture Notes in Computer Science, vol 14395. Springer, Cham. https://doi.org/10.1007/978-3-031-47859-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-47859-8_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-47858-1
Online ISBN: 978-3-031-47859-8
eBook Packages: Computer ScienceComputer Science (R0)