Дослідження методів розв`язання NP-повних задач на прикладі задачі про перекриття точок колами заданого радіуса

Abstract

The publication is devoted to the study of methods for solving the problem of covering a set of points of the minimum number of circles of a given radius. The practical application of this problem and the basic principles of the approach to its solution are considered. Two algorithms for its solution are also described and their complexity is evaluated.

Публікація присвячена дослідженню методів вирішення задачі про покриття набору точок мінімальною кількістю кіл заданого радіуса. Розглянуто практичне застосування цієї задачі та базові принципи підходу до її розв’язання. Також описано два алгоритми її розв’язку та оцінено їх складність