Нові інваріанти встановлення ізоморфізму графів

Loading...
Thumbnail Image

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 назв.

Endorsement

Review

Supplemented By

Referenced By