О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом

• Published in: Екологічна безпека та природокористування
• Date: 2009
• Main Author: Васянин, В.А.
• Format: Article
• Language: Russian
• Published: Інститут телекомунікацій і глобального інформаційного простору НАН України 2009
• Subjects: Науково-технологiчна безпека
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/19386
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: О вычислительной эффективности одного алгоритма для нахождения остовного леса графа с минимальным (максимальным) весом / В.А. Васянин // Екологічна безпека та природокористування: Зб. наук. пр. — К., 2009. — Вип. 4. — С. 155-169. — Бібліогр.: 12 назв. — рос.

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...