This article is cited in 1 paper

Information Technology Applications in Control

Algorithm for dynamic all-pairs distances in graph

A. R. Urakov, T. V. Timeryaev

Ufa State Aviation Technical University

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

Keywords: dynamic graph distances, graph update, equidistant points, graph actualization.

UDC: 519.178
BBK: 22.176

Received: August 16, 2016
Published: January 31, 2017

Bibliographic databases:

•