Алгоритм проверки изоморфизма деревьев Хусими

Abstract

В данной работе строится полиномиальный алгоритм для проверки изоморфизма деревьев Хусими, т. е. связных графов, у которых каждый блок является либо ребром, либо циклом. Построенный нами алгоритм работает за время Q (n2), где n - порядок дерева Хусими.

We introduce a polynomial algorithm for testing isomorphism of a given pair of Husimi trees. A Husimi tree is connected simple graph whose blocks are either edges or cyclic paths. The time complexity of the algorithm is Q (n2).