A practical solution of some NP-hard software configuration problem

Аuthors

Romanova T. N.^*, Anisimov A. V.^**

Bauman Moscow State Technical University, MSTU, 5, bldg. 1, 2-nd Baumanskaya str., Moscow, 105005, Russia

*e-mail: rtn@bmstu.ru
**e-mail: alan_mephi@mail.ru

Abstract

A mathematical statement of structural synthesis problem is presented as applies to software engineering field. Two versions oj the problem are discussed relating to various complexity classes as well as techniques needed to solve appropriate problems. A comparative analysis is carried out for the considered problems.

Keywords:

structural synthesis; set theory; optimization on graphs; NP-hardness; approximate method; local improvement method; exhaustive search; Rado—Edmonds greedy algorithm; combinatorially optimization problem; asymptotic computational complexity estimation