Алгоритм знаходження найбільшого загального підграфа
A new enumerating algorithm for the solution of the problem of finding a maximal common subgraph is proposed. The results are presented for the numerical analysis of the algorithm efficiency on graphs of different classes and sizes, which compose the graph database for estimation of the efficiency o...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2009
|
| Online Zugang: | http://journal.iasa.kpi.ua/article/view/108438 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
Institution
System research and information technologies| _version_ | 1856543292989112320 |
|---|---|
| author | Ilyashenko, M. B. |
| author_facet | Ilyashenko, M. B. |
| author_sort | Ilyashenko, M. B. |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2018-04-06T12:34:45Z |
| description | A new enumerating algorithm for the solution of the problem of finding a maximal common subgraph is proposed. The results are presented for the numerical analysis of the algorithm efficiency on graphs of different classes and sizes, which compose the graph database for estimation of the efficiency of algorithms for solving problems concerning morphism on graphs. The potential of using the algorithm in solving real-world problems on graphs sizing up to several hundreds of vertices is estimated. |
| first_indexed | 2025-07-17T10:22:40Z |
| format | Article |
| id | journaliasakpiua-article-108438 |
| institution | System research and information technologies |
| language | Russian |
| last_indexed | 2025-07-17T10:22:40Z |
| publishDate | 2009 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| spelling | journaliasakpiua-article-1084382018-04-06T12:34:45Z Algorithm for finding maximal common subgraph Алгоритм нахождения наибольшего общего подграфа Алгоритм знаходження найбільшого загального підграфа Ilyashenko, M. B. A new enumerating algorithm for the solution of the problem of finding a maximal common subgraph is proposed. The results are presented for the numerical analysis of the algorithm efficiency on graphs of different classes and sizes, which compose the graph database for estimation of the efficiency of algorithms for solving problems concerning morphism on graphs. The potential of using the algorithm in solving real-world problems on graphs sizing up to several hundreds of vertices is estimated. Предлагается новый переборный алгоритм решения задачи нахождения наибольшего общего подграфа. Приведены результаты численного анализа производительности алгоритма на графах различных классов и размеров, входящих в состав базы графов для оценки производительности алгоритмов решения задач установления морфизма на графах. Дана оценка потенциала применения разработанного алгоритма для решения реальных прикладных задач на графах размером порядка сотен вершин. Запропоновано новий переборний алгоритм вирішення задачі знаходження найбільшого загального підграфа. Наведено результати чисельного аналізу продуктивності алгоритму на графах різних класів та розмірів, що складають базу графів для оцінки продуктивності алгоритмів вирішення задач встановлення морфізму на графах. Надана оцінка потенціалу застосування розробленого алгоритму для вирішення реальних задач на графах розміром до декількох сотень вершин. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2009-06-19 Article Article Peer-reviewed Article application/pdf http://journal.iasa.kpi.ua/article/view/108438 System research and information technologies; No. 2 (2009); 112-120 Системные исследования и информационные технологии; № 2 (2009); 112-120 Системні дослідження та інформаційні технології; № 2 (2009); 112-120 2308-8893 1681-6048 ru http://journal.iasa.kpi.ua/article/view/108438/103388 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Ilyashenko, M. B. Алгоритм знаходження найбільшого загального підграфа |
| title | Алгоритм знаходження найбільшого загального підграфа |
| title_alt | Algorithm for finding maximal common subgraph Алгоритм нахождения наибольшего общего подграфа |
| title_full | Алгоритм знаходження найбільшого загального підграфа |
| title_fullStr | Алгоритм знаходження найбільшого загального підграфа |
| title_full_unstemmed | Алгоритм знаходження найбільшого загального підграфа |
| title_short | Алгоритм знаходження найбільшого загального підграфа |
| title_sort | алгоритм знаходження найбільшого загального підграфа |
| url | http://journal.iasa.kpi.ua/article/view/108438 |
| work_keys_str_mv | AT ilyashenkomb algorithmforfindingmaximalcommonsubgraph AT ilyashenkomb algoritmnahoždeniânaibolʹšegoobŝegopodgrafa AT ilyashenkomb algoritmznahodžennânajbílʹšogozagalʹnogopídgrafa |