Алгоритмы быстрого поиска для двух задач о метрических характеристиках взвешенных графов

Ураков Айрат Ренатович and Тимеряев Тимофей Валерьевич
Additional contact information
Ураков Айрат Ренатович: Уфимский государственный авиационный технический университет
Тимеряев Тимофей Валерьевич: Уфимский государственный авиационный технический университет

Управление большими системами: сборник трудов, 2013, issue 42, 153-172

Abstract: Рассматриваются две задачи о поиске метрических характеристик взвешенных неориентированных графов с неотрицательными весами ребер. Первая задача: дан взвешенный неориентированный граф, требуется найти радиус, диаметр и хотя бы один центр и две периферийные вершины. Во второй задаче дополнительно задана матрица расстояний графа. Для рассматриваемых задач предлагаются алгоритмы быстрого поиска, которые для поиска указанных характеристик посматривают лишь часть вершин графа. Приводится сравнение предлагаемых алгоритмов с популярными способами решения поставленных задач на различных исходных данных.

Keywords: МЕТРИЧЕСКИЕ ХАРАКТЕРИСТИКИ ГРАФА; РАДИУС ГРАФА; ДИАМЕТР ГРАФА; ЦЕНТР ГРАФА; ПЕРИФЕРИЙНЫЕ ВЕРШИНЫ ГРАФА (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://cyberleninka.ru/article/n/algoritmy-bystrog ... h-vzveshennyh-grafov

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:scn:022092:14467637

Access Statistics for this article

More articles in Управление большими системами: сборник трудов from CyberLeninka, Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова РАН
Bibliographic data for series maintained by CyberLeninka ().