Нові інваріанти встановлення ізоморфізму графів
No Thumbnail Available
Files
Date
2008
Journal Title
Journal ISSN
Volume Title
Publisher
Видавництво Національного університету "Львівська політехніка"
Abstract
Проблеми встановлення ізоморфізму графів стосується доволі велика кількість робіт, одними з найхарактерніших є [1–4]. Низка узагальнень наводиться також у таких роботах, як [5–9]. Показано [3], що подібні задачі є комбінаторними важкорозв’язуваними задачами факторіального ступеня складності, у зв’язку з чим для їхнього розв’язання прийнятними залишаються лише евристичні прийоми [1, 10, 11]. Тому тут не будуть ефективними ні метод гілок і границь, ні методи математичногом програмування, які у кращому випадку понижують складність задачі від факторіальної залежності до показникової (відносно, як правило, кількості вершин графа), а це є неприйнятним для задач практичної розмірності. Водночас існуючі евристичні прийоми розв’язання задачі (а точніше, спроби її розв’язання) мають, як правило, часову складність
O(Nc), де с=4¸6 [3, 8], що також різко обмежує розмірність задач, які розв’язуються, оскільки
для розв’язання задач за прийнятний час необхідно, щоб було с≤3.
Description
Keywords
Citation
Нові інваріанти встановлення ізоморфізму графів / Білаль Раді А’Ґґель Аль-Забі, А. Б. Керницький, М. В. Лобур, С. П. Ткаченко // Вісник Національного університету "Львівська політехніка". – 2008. – № 626 : Комп'ютерні системи проектування. Теорія і практика. – С. 90–93. – Бібліографія: 14 назв.