Алгоритм поиска наибольшего независимого множества

В статье представлен алгоритм MaxIS для поиска наибольшего независимого множества в неориентированном графе. Эта задача принадлежит к числу так называемых NP-полных задач, что означает отсутствие в настоящее время алгоритмов, решающих ее за полиномиальное время. Несмотря на то что рассматриваемый алгоритм также не является полиномиальным, он находит решение быстрее, чем тривиальный алгоритм полного перебора. Каждая ветвь дерева поиска, построенного по алгоритму MaxIS, соответствует уникальному максимальному независимому множеству. Приведены результаты сравнения работы предложенного алгоритма с алгоритмом Робсона, считающимся в настоящее время одним из лучших алгоритмов для решения вышеуказанной задачи. Тестирование алгоритмов было проведено на некотором наборе произвольных графов с различными значениями плотности. Библиогр. 6 назв. Ил. 4.