УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта


јвтор:  ”раков ј. –., “имер€ев “. ¬.
Ќазвание:  јлгоритмы быстрого поиска дл€ двух задач о метрических характеристиках взвешенных графов
¬ыпуск:  42
–убрика:  »нформационные технологии в управлении
√од:  2012
Ѕиблиографи€:  ”раков ј. –., “имер€ев “. ¬. јлгоритмы быстрого поиска дл€ двух задач о метрических характеристиках взвешенных графов / ”правление большими системами. ¬ыпуск 42. ћ.: »ѕ” –јЌ, 2013. —.153-172.
 лючевые слова:  метрические характеристики графа, радиус графа, диаметр графа, центр графа, периферийные вершины графа
 лючевые слова (англ.):  metric characteristics of a graph, graph radius, graph diameter, graph center, graph peripheral vertices
јннотаци€:  –ассматриваютс€ две задачи о поиске метрических характеристик взвешенных неориентированных графов с неотрицательными весами ребер. ѕерва€ задача: дан взвешенный неориентированный граф, требуетс€ найти радиус, диаметр и хот€ бы один центр и две периферийные вершины. ¬о второй задаче дополнительно задана матрица рассто€ний графа. ƒл€ рассматриваемых задач предлагаютс€ алгоритмы быстрого поиска, которые дл€ поиска указанных характеристик посматривают лишь часть вершин графа. ѕриводитс€ сравнение предлагаемых алгоритмов с попул€рными способами решени€ поставленных задач на различных исходных данных.
јннотаци€ (англ.):  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
ќбсудить статью в »нтернет-конференции по проблемам управлени€

ѕросмотров: 2976, загрузок: 941, за мес€ц: 24.

Ќазад

»ѕ” –јЌ © 2007. ¬се права защищены