About using special data structures in coverage algorithms

O.N. Paulin, N.O. Komleva


The aim of this work is to increase the efficiency of methods and algorithms for solving the problem of finding coverage. Efficiency is understood as the minimum delay of the procedure that implements this method. To increase the efficiency of the “Columnization” method, a characteristic vector (CV) is introduced into the decision tree construction procedure, obtained by summing the units in columns / rows of the coverage table (CT); it characterizes the current state of the coverage table. The idea of this method is to gradually decompose CT into sub-tables using their reduction according to certain rules. We consider 3 ways to reduce the original table / current sub-tables in the methods: 1) "Border search over a concave set"; 2) "Using the properties of the coverage table"; 3) "The minimum column is the maximum row." In the latter method, CV was used for the first time, which made it possible to accelerate the coating finding procedure up to one and a half times. The complexity estimates for the considered coating methods are calculated; we have: S1 = O (n ^ 3); S2 = O (2 ^ n); S3 = O (n ^ 2), where n is the determining parameter of the coverage problem (number of columns), and the applicability limits of these methods are determined. It is shown that the use of CV in methods 1 and 2 is impractical.

Problems in programming 2020; 2-3: 138-148


coverage; efficiency, method; decision tree; characteristic vector; reduction of the coverage table; assessment of the complexity of the procedure


Mathur A.P. (2013) Foundations of software testing: fundamental algorithms and techniques. New Delhi: Dorling Kindersley. 324 p.

Mansoor A. (2013) Automated Software Test Data Optimization Using Artificial Intelligence. Int. J. Inf. Commun. Technol. Trends. 9. P. 5-19.

Ahuja K. & Khosla A. (2019) A novel framework for data acquisition and ubiquitous communication provisioning in smart cities. Future Generation Computer Systems - The International Journal Of Science. 101. P. 785-803. CrossRef

Sanchez-Gomez J.M., Vega-Rodríguez M.A. & Pérez C.J. (2019) Parallelizing a multi-objective optimization approach for extractive multi-document text summarization. Journal of Parallel and Distributed Computing. 134. P. 166-179. CrossRef

Zhanyang X., Xihua L., Gaoxing J. & Bowei T. (2019) A time-efficient data offloading method with privacy preservation for intelligent sensors in edge computing. Eurasip Journal On Wireless Communications And Networking. 1. P. 236- 46. CrossRef

Hui L., Haining L., Shu Z., Zhaoman Z. & Jiang C. (2019) Intelligent learning system based on personalized recommendation technology. Neural Computing & Applications. 31 (9). P. 4455-4462. CrossRef

Kuzyurin N.N. & Fomin S.A. (2011) Efficient algorithms and computational complexity. Kyiv. 363 p.

Sergeev A.P. (2010) Algorithm for determining isomorphism of XML schemas. Program problems. 2-3. P. 530-536.

Prohorov V.G. (2007) Recognition of graphic images of text characters represented in the form of characteristic vectors. Program problems. 3. P. 97-106.

Paulin O.N. (2016) Computational models of coverage algorithms. Computer science and mathematical methods in modeling. 6 (4). P. 385-396.

Paulin O.N. (2017) Methods and algorithms for coverage (Part 2). Computer science and mathematical methods in modeling. 7 (4). P. 333-338.

Kancedal S.A. & Kostikova M.V. (2011) One algorithm for solving the coverage problem. Automated control systems and automation devices. 155. P. 49-53.

Paulin О.N., Коmleva N.О, Sinegub N.I. & Sarafaniuk D.E. (2020) About modification the coverage algorithm using the "minimum column - maximum row" method. Scientific notes of TNU Vernadsky. Series: Technical Sciences.. Т. 31 (70), N 1. (in press) CrossRef

Novosyolov V.G. & Skatkov A.V. (1992) Applied Mathematics for Systems Engineers. Discrete Mathematics in Problems and Examples: A Study Guide. Kyiv. 200 p.

DOI: https://doi.org/10.15407/pp2020.02-03.138


  • There are currently no refbacks.