Будь ласка, використовуйте цей ідентифікатор, щоб цитувати або посилатися на цей матеріал: http://ena.lp.edu.ua:8080/handle/ntb/530
Назва: Нові інваріанти встановлення ізоморфізму графів
Автори: Білаль Раді А’Ґґель Аль-Забі
Керницький, А. Б.
Лобур, М. В.
Ткаченко, С. П.
Бібліографічний опис: Нові інваріанти встановлення ізоморфізму графів / Білаль Раді А’Ґґель Аль-Забі, А. Б. Керницький, М. В. Лобур, С. П. Ткаченко // Вісник Національного університету "Львівська політехніка". – 2008. – № 626 : Комп'ютерні системи проектування. Теорія і практика. – С. 90–93. – Бібліографія: 14 назв.
Дата публікації: 2008
Видавництво: Видавництво Національного університету "Львівська політехніка"
Короткий огляд (реферат): Проблеми встановлення ізоморфізму графів стосується доволі велика кількість робіт, одними з найхарактерніших є [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
Тип вмісту : Article
Розташовується у зібраннях:Комп'ютерні системи проектування теорія і практика. – 2008. – №626

Файли цього матеріалу:
Файл Опис РозмірФормат 
14.pdf147,73 kBAdobe PDFПереглянути/відкрити


Усі матеріали в архіві електронних ресурсів захищені авторським правом, всі права збережені.