On the quick search for the shortest paths in an unweighted dynamic graph by its projections in brief

arXiv2206.03757MaRDI QIDQ6401442FDOQ6401442

Authors: V. A. Melent'ev 

Publication date: 8 June 2022

Abstract: For the first time proposed: a method for representing the projections of a graph in computer memory and a description based on it of a quick search for shortest paths in unweighted dynamic graphs. The spatial complexity of the projection description does not exceed $(d+1)imesn$ words, where $d$ is the diameter and $n$ is the number of vertices of the graph. The temporal difficulty of finding one shortest path between two vertices does not exceed d steps with the duration of elementary time of sampling a machine word. The solution can be applied in time delay-critical routing protocols of computer networks and supercomputers.

This page was built for publication: On the quick search for the shortest paths in an unweighted dynamic graph by its projections in brief

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401442)