Graph-Connectivity Algorithms for External Memory Model

One of the models in which algorithms are considered is the external memory model. It is used when the size of the input data of the algorithm is many times larger than the size of the computer's RAM. In this case, the input date is usually stored on the hard disk and read by blocks. These read operations are expensive and often takes more time than computational operations. In the external memory model, the complexity of an algorithm is measured in terms of the number of read/write operations (I/O) from the hard disk. At the same time, the number of operations with the internal memory is not taken into account in the complexity of the algorithm, since they are performed much faster. In this final qualifying work, we consider algorithms on graphs. For undirected graphs, there are exist many efficient algorithms to solve classical graph problems. So, for example, they know how to efficiently find the path between two vertices, as well as find the connected components. For directed graphs until 2019, there were no algorithms using less than | V | I / O operations. However, in 2019, an algorithm was proposed that allows you to effectively find the topological sort of an acyclic graph, as well as find the strongly connected components of an arbitrary graph. In this paper, we consider the problem of finding a path between any two vertices in an arbitrary directed graph. An algorithm was invented that solves this problem quite efficiently. As a basis for the algorithm, ideas were taken from an article on topological sorting of a graph. The pathfinding algorithm builds some data structure along the graph, with the help of which it is possible to further respond to requests for finding a path between arbitrary vertices. Also, an algorithm was invented that allows you to handle inserts of edges into the graph in order to respond to subsequent requests for finding a path in the updated graph. For all algorithms, a detailed description is given, and the complexity of work in the external memory model is also proved.