Предложен метод поиска наибольших максимальных независимых множеств неориентированного связного графа, позволяющий при числе вершин в графе, не превышающем 120, и плотностях ребер в диапазоне от 0,067 до 0,9, решать задачу определения наибольших максимальных независимых множеств за полиномиальное время. При дальнейшем увеличении числа вершин и уменьшении плотности ребер в графе алгоритм имеет экспоненциальную сложность, в среднем не превышающую О(2<^>0,4n), которая имеет тенденцию к уменьшению при увеличении плотности ребер в графе, где n - число вершин графа.