Алгоритм перевірки графів на ізомофність з використанням локальних інваріантів
eKMAIR
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Алгоритм перевірки графів на ізомофність з використанням локальних інваріантів
Algorithm for Graph Isomorphism Based on Local Invariants |
|
| Creator |
Чичкань, Сергій
|
|
| Subject |
вхідні дані
впорядкування ізомофність вершинний інваріант |
|
| Description |
Одним із способів зниження часової складності перевірних задач є впорядкування множини вхідних даних, що дає змогу ідентифікувати їх незалежно від порядку зберігання чи переліку. Для цього кожному елементу множини приписується чисельна характеристика (вага). Якщо метою перебору є встановлення еквівалентності двох множин і всім елементам множини можна приписати різну вагу, швидке сортування обох множин за час O(Nlog2N) практично розв 'язує задачу, оскільки після впорядкування залишається за час 0(N) перевірити еквівалентність упорядкованих масивів, які містять елементи множини. У цій роботі наведено алгоритм перевірки графів на ізоморфність, що базується на впорядкуванні вершинних інваріантів локального порядку.
|
|
| Date |
2016-02-17T08:27:58Z
2016-02-17T08:27:58Z 2003 |
|
| Type |
Article
|
|
| Identifier |
Чичкань Сергій Михайлович. Алгоритм перевірки графів на ізомофність з використанням локальних інваріантів / С. М. Чичкань // Наукові записки НаУКМА : Комп'ютерні науки. - 2003. - Т. 21. - С. 5-10.
http://ekmair.ukma.edu.ua/handle/123456789/8413 |
|
| Language |
ua
|
|
| Relation |
Наукові записки НаУКМА: Комп'ютерні науки
|
|