О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом
In work effective realization of «greedy» algorithm for finding minimum (maximum) spanning woods (trees) of an undirected weighed graph is considered. Is given the rating of the expected computing time of algorithm is 0 (M), where M — number of edges in a graph. Is shown, that the offered algorithm...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут телекомунікацій і глобального інформаційного простору НАН України
2009
|
| Назва видання: | Екологічна безпека та природокористування |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/19386 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом / В.А. Васянин // Екологічна безпека та природокористування: Зб. наук. пр. — К., 2009. — Вип. 4. — С. 155-169. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-19386 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-193862011-04-28T12:04:36Z О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом Васянин, В.А. Науково-технологiчна безпека In work effective realization of «greedy» algorithm for finding minimum (maximum) spanning woods (trees) of an undirected weighed graph is considered. Is given the rating of the expected computing time of algorithm is 0 (M), where M — number of edges in a graph. Is shown, that the offered algorithm is better than a Prim’s algorithm for graphs with number of edges less, than N2/6, where N — number of vertices in a graph. The experimental research of algorithm on the graphs, containing from 499500 up to 71994000 edges, has shown its high computing efficiency and his can be recommended for the decision of practical problems on rarefied graphs or networks of the big dimension. 2009 Article О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом / В.А. Васянин // Екологічна безпека та природокористування: Зб. наук. пр. — К., 2009. — Вип. 4. — С. 155-169. — Бібліогр.: 12 назв. — рос. XXXX-0062 http://dspace.nbuv.gov.ua/handle/123456789/19386 519.1 ru Екологічна безпека та природокористування Інститут телекомунікацій і глобального інформаційного простору НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Науково-технологiчна безпека Науково-технологiчна безпека |
| spellingShingle |
Науково-технологiчна безпека Науково-технологiчна безпека Васянин, В.А. О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом Екологічна безпека та природокористування |
| description |
In work effective realization of «greedy» algorithm for finding minimum (maximum) spanning woods (trees) of an undirected weighed graph is considered. Is given the rating of the expected computing time of algorithm is 0 (M), where M — number of edges in a graph. Is shown, that the offered algorithm is better than a Prim’s algorithm for graphs with number of edges less, than N2/6, where N — number of vertices in a graph. The experimental research of algorithm on the graphs, containing from 499500 up to 71994000 edges, has shown its high computing efficiency and his can be recommended for the decision of practical problems on rarefied graphs or networks of the big dimension. |
| format |
Article |
| author |
Васянин, В.А. |
| author_facet |
Васянин, В.А. |
| author_sort |
Васянин, В.А. |
| title |
О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом |
| title_short |
О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом |
| title_full |
О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом |
| title_fullStr |
О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом |
| title_full_unstemmed |
О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом |
| title_sort |
о вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом |
| publisher |
Інститут телекомунікацій і глобального інформаційного простору НАН України |
| publishDate |
2009 |
| topic_facet |
Науково-технологiчна безпека |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/19386 |
| citation_txt |
О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом / В.А. Васянин // Екологічна безпека та природокористування: Зб. наук. пр. — К., 2009. — Вип. 4. — С. 155-169. — Бібліогр.: 12 назв. — рос. |
| series |
Екологічна безпека та природокористування |
| work_keys_str_mv |
AT vasâninva ovyčislitelʹnojéffektivnostiodnogoalgoritmadlânahoždeniâostovnogolesagrafasminimalʹnymmaksimalʹnymvesom |
| first_indexed |
2023-10-18T17:04:32Z |
| last_indexed |
2023-10-18T17:04:32Z |
| _version_ |
1796140612803624960 |