Том 11, серия 1, номер 3, 2004 г., Стр. 63-79

УДК 519.175
О. В. Расин
Цепные разложения по расстоянию и изоморфизмы графов

Аннотация:
Пусть $d$ – некоторая натуральная константа. Обозначим через $\mathcal G_d$ класс всех связных графов, в которых степени вершин не превосходят $d$. В этой статье строится полиномиальный алгоритм проверки изоморфизма для класса графов, которые обладают цепными разложениями по расстоянию с одноэлементным корневым множеством и компонентами из класса $\mathcal G_d$.

Расин О. В. ¹
1. Уральский гос. университет,
пр. Ленина, 51, 620083 Екатеринбург, Россия
е-mail: ovr@r66.ru

Статья поступила 2 марта 2003 г.
Исправленный вариант — 26 февраля 2004 г.