Алгоритмы обнаружения изоморфизма подграфа
Изоморфизм подграфа является полной проблемой NP. Наиболее широко используемый алгоритм - это алгоритм, предложенный Уллманом.
Может кто-нибудь объяснить мне алгоритм на языке непрофессионала? Я прочитал вышеупомянутую статью им, но не мог понять многое.
Какие еще алгоритмы существуют для этой проблемы?
Я работаю над проектом обработки изображений.
2 ответа
Решение
VFLib2 - это библиотека C++ для нахождения изоморфизма графов. Он также включает реализацию Ullman: http://mivia.unisa.it/datasets/graph-database/vflib/
Этот пост в блоге пытается дать обзор алгоритма. Оригинальную презентацию трудно прочитать, потому что она представляет алгоритм, как если бы вы написали его на компьютере 70-х годов.