Please use this identifier to cite or link to this item: http://ena.lp.edu.ua:8080/handle/ntb/530
Title: Нові інваріанти встановлення ізоморфізму графів
Authors: Білаль Раді А’Ґґель Аль-Забі
Керницький, А. Б.
Лобур, М. В.
Ткаченко, С. П.
Bibliographic description (Ukraine): Нові інваріанти встановлення ізоморфізму графів / Білаль Раді А’Ґґель Аль-Забі, А. Б. Керницький, М. В. Лобур, С. П. Ткаченко // Вісник Національного університету "Львівська політехніка". – 2008. – № 626 : Комп'ютерні системи проектування. Теорія і практика. – С. 90–93. – Бібліографія: 14 назв.
Issue Date: 2008
Publisher: Видавництво Національного університету "Львівська політехніка"
Abstract: Проблеми встановлення ізоморфізму графів стосується доволі велика кількість робіт, одними з найхарактерніших є [1–4]. Низка узагальнень наводиться також у таких роботах, як [5–9]. Показано [3], що подібні задачі є комбінаторними важкорозв’язуваними задачами факторіального ступеня складності, у зв’язку з чим для їхнього розв’язання прийнятними залишаються лише евристичні прийоми [1, 10, 11]. Тому тут не будуть ефективними ні метод гілок і границь, ні методи математичногом програмування, які у кращому випадку понижують складність задачі від факторіальної залежності до показникової (відносно, як правило, кількості вершин графа), а це є неприйнятним для задач практичної розмірності. Водночас існуючі евристичні прийоми розв’язання задачі (а точніше, спроби її розв’язання) мають, як правило, часову складність O(Nc), де с=4¸6 [3, 8], що також різко обмежує розмірність задач, які розв’язуються, оскільки для розв’язання задач за прийнятний час необхідно, щоб було с≤3.
URI: http://ena.lp.edu.ua:8080/handle/ntb/530
Content type: Article
Appears in Collections:Комп'ютерні системи проектування теорія і практика. – 2008. – №626

Files in This Item:
File Description SizeFormat 
14.pdf147,73 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.