Каркасный алгоритм оценки схожести невзвешенных неориентированных графов - Sysoev, Valentin Valeryevich (Современные информационные технологии и ИТ-образование, 2022)
Общеизвестно, что проблема алгоритмов оценки схожести графов упирается в сложность их вычисления. Большинство предлагаемых алгоритмов оценки схожести графов основаны на алгоритме Ульмана. Философия алгоритма Ульмана заключается в работе с матрицами смежности. Алгоритм Ульмана имеет высокую сложность вычисления, применение параллельных вычислений, в том числе, на видеокартах, оставляет алгоритм Ульмана   NP – сложным. При этом алгоритм Ульмана дает только информацию, изоморфны ли графы или является ли один из них подграфом другого, а для получения численной оценки схожести необходимо проводить дополнительные вычисления. Предлагаемый в статье каркасный алгоритм оценки схожести призывает отойти от философии алгоритма Ульмана, а именно, работы с матрицами смежности. Новый алгоритм основан на построении и изучении каркасов сравниваемых графов. В статье приводится определение и алгоритм построения каркаса графа, который, в свою очередь, строятся на основе ранее опубликованном итерационном алгоритме нахождения всех наикратчайших путей между двумя вершинами. Каркасный алгоритм имеет асимптотическую сложность  O(|V| 2 ), способен выявить гомоморфизм графов и дать количественную оценку схожести двух сравниваемых графов.