Engineering Journal: Science and InnovationELECTRONIC SCIENCE AND ENGINEERING PUBLICATION
Certificate of Registration Media number Эл #ФС77-53688 of 17 April 2013. ISSN 2308-6033. DOI 10.18698/2308-6033
  • Русский
  • Английский
Article

Ways to reduce computational complexity of the algorithms follow from the principle of creating solutions

Published: 19.11.2013

Authors: Ovchinnikov V.A.

Published in issue: #11(23)/2013

DOI: 10.18698/2308-6033-2013-11-1046

Category: Information technology

The article describes one of the classes ways to reduce the computational complexity of combinatorial optimization algorithms on graphs and sets. Consideration of methods based on the use of the principle of step-forming solutions. A classification group of these methods is given. Examples are considered to fulfillment of optimizing transformations in the iterations algorithm to improve the hypergraph cutting and sequential algorithm of its initial cut. The processes and formulas for determining the values of criteria and the vertex set of candidate these algorithms are discussed. We obtained estimates of the computational complexity of the above action for the cases with and without the use of methods to reduce the computational complexity. The evaluation of the effectiveness of these methods is performed. A possibility of formalizing consideration of optimizing transformations is determined.