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

Автор(ы): Ураков А. Р., Тимеряев Т. В.

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

Выпуск: 42

Рубрика: Информационные технологии в управлении

Год: 2012

Библиография: Ураков А. Р., Тимеряев Т. В. Алгоритмы быстрого поиска для двух задач о метрических характеристиках взвешенных графов / Управление большими системами. Выпуск 42. М.: ИПУ РАН, 2013. С.153-172.

Дата опубликования: 31.03.2013

Ключевые слова: метрические характеристики графа, радиус графа, диаметр графа, центр графа, периферийные вершины графа

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

Author(s): Urakov A., Timeryaev T.

Article title: Fast search algorithms for two metric characteristics problems on weighted graphs

Issue: 42

Year: 2012

Keywords: metric characteristics of a graph, graph radius, graph diameter, graph center, graph peripheral vertices

Abstract: Two problems are considered of metric characteristics search on weighted undirected graphs with non-negative edge weights. The first problem is to find the radius, diameter, at least one center, and one pair of peripheral vertices of an undirected graph with non-negative edge weights. In the second problem one also has the pre-calculated distances matrix. For these problems we propose fast search algorithms, which use only small fraction of graph vertices for metric characteristics search. The proposed algorithms are tested on various inputs against the other popular methods.

в формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 5576; загрузок: 1753, за месяц: 20.

Назад