Нахождение всех максимальных независимых множеств неориентированного графа

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