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


јвтор:  ”раков ј.–., “имер€ев “.¬.
Ќазвание:  јлгоритм решени€ динамической задачи поиска кратчайших рассто€ний в графе
¬ыпуск:  65
–убрика:  »нформационные технологии в управлении
√од:  2017
Ѕиблиографи€:  ”раков ј.–., “имер€ев “.¬. јлгоритм решени€ динамической задачи поиска кратчайших рассто€ний в графе / ”правление большими системами. ¬ыпуск 65. ћ.: »ѕ” –јЌ, 2017. —.60-86. URL: https://doi.org/10.25728/ubs.2017.65.4
 лючевые слова:  динамические кратчайшие рассто€ни€, актуализаци€ графа, коррекци€ графа, равноудаленные точки
 лючевые слова (англ.):  dynamic graph distances, graph update, equidistant points, graph actualization
јннотаци€:  –ассматриваетс€ полностью динамическа€ задача поиска кратчайших рассто€ний между всеми парами вершин неориентированного графа. ƒл€ данной задачи предлагаетс€ метод решени€, учитывающий все возможные изменени€ рассто€ний в графе с помощью процедур добавлени€ и удалени€ ребра. ƒл€ процедуры удалени€ ребра предложен алгоритм, использующий пон€тие точек, равноудаленных от вершин, инцидентных удал€емому ребру. јлгоритм позвол€ет существенно уменьшить врем€ решени€ и объем используемой пам€ти в практических сценари€х. ƒл€ доказательства практической эффективности предложенного метода решени€ произведен вычислительный эксперимент с использованием известных быстрых статических и динамических алгоритмов.
јннотаци€ (англ.):  Fully dynamic all-pairs graph distances problem for undirected graphs with positive edge weights is considered. Edge weights can change arbitrary so distances between vertices should be kept actual. We propose an algorithm taking into account all possible distance changes by the use of edge addition and deletion procedures. The developed algorithm uses the notion of points equidistant to the vertices incident to the edge being deleted for an edge deletion procedure. This allows to significantly reduce time and memory complexity of the graph distance actualization task in practical scenarios. The conducted computational experiments showed that the proposed algorithms outperforms the fastest known methods.

в формате PDF
ќбсудить статью в »нтернет-конференции по проблемам управлени€

ѕросмотров: 1094, загрузок: 463, за мес€ц: 21.

Ќазад

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