Нові інваріанти встановлення ізоморфізму графів
Електронний науковий архів Науково-технічної бібліотеки Національного університету "Львівська політехніка"
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Нові інваріанти встановлення ізоморфізму графів
|
|
| Creator |
Білаль Раді А’Ґґель Аль-Забі
Керницький, А. Б. Лобур, М. В. Ткаченко, С. П. |
|
| Description |
Проблеми встановлення ізоморфізму графів стосується доволі велика кількість робіт, одними з найхарактерніших є [1–4]. Низка узагальнень наводиться також у таких роботах, як [5–9]. Показано [3], що подібні задачі є комбінаторними важкорозв’язуваними задачами факторіального ступеня складності, у зв’язку з чим для їхнього розв’язання прийнятними залишаються лише евристичні прийоми [1, 10, 11]. Тому тут не будуть ефективними ні метод гілок і границь, ні методи математичногом програмування, які у кращому випадку понижують складність задачі від факторіальної залежності до показникової (відносно, як правило, кількості вершин графа), а це є неприйнятним для задач практичної розмірності. Водночас існуючі евристичні прийоми розв’язання задачі (а точніше, спроби її розв’язання) мають, як правило, часову складність O(Nc), де с=4¸6 [3, 8], що також різко обмежує розмірність задач, які розв’язуються, оскільки для розв’язання задач за прийнятний час необхідно, щоб було с≤3. |
|
| Date |
2009-09-04T07:17:59Z
2009-09-04T07:17:59Z 2008 |
|
| Type |
Article
|
|
| Identifier |
Нові інваріанти встановлення ізоморфізму графів / Білаль Раді А’Ґґель Аль-Забі, А. Б. Керницький, М. В. Лобур, С. П. Ткаченко // Вісник Національного університету "Львівська політехніка". – 2008. – № 626 : Комп'ютерні системи проектування. Теорія і практика. – С. 90–93. – Бібліографія: 14 назв.
http://ena.lp.edu.ua:8080/handle/ntb/530 |
|
| Publisher |
Видавництво Національного університету "Львівська політехніка"
|
|