Про часову складність алгоритму розкладання графів на різних структурах даних
Для представлення графів у вигляді матриць суміжності та натуральних арифметичних графів проведено оцінку часових складностей алгоритму розкладання графів за допомогою їх кістяків, здійснено порівняння цих складностей. Предложен алгоритм декомпозиции графов с помощью их остовов. Рассмотрено два спос...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84688 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Про часову складність алгоритму розкладання графів на різних структурах даних / Т.О. Гришанович, О.О. Провотар // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 60-68. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Summary: | Для представлення графів у вигляді матриць суміжності та натуральних арифметичних графів проведено оцінку часових складностей алгоритму розкладання графів за допомогою їх кістяків, здійснено порівняння цих складностей.
Предложен алгоритм декомпозиции графов с помощью их остовов. Рассмотрено два способа представления графов: матрица смежности и натуральные арифметические графы. Проведено оценку временной сложности данного алгоритма для этих способов, приведено их сравнение.
An algorithm of decomposition of graphs using their skeletons is proposed. Adjacency matrix and natural arithmetic graphs with three generatrices are considered. Time complexity of decomposition algorithms for these data structures is evaluated.
|
|---|---|
| ISSN: | ХХХХ-0003 |