External memory algorithms for finding disjoint paths in undirected graphs(

P. 295–304.

Babenko M. A., Колесниченко И. И.

Consider the following well-known combinatorial problem: given an undirected graph G= (V, E), terminals s, t∈ V, and an integer k≥ 1, find k edge-disjoint s–t paths in G or report that such paths do not exist. We study this problem in the external memory (EM) model of Agrawal and Vitter, i.e. assume that only M words of random access memory (RAM) are available while the graph resides in EM, which enables reading and writing contiguous blocks of B words per single I/O. The latter external memory is also used for storing the output and some intermediate data. For k= 1, the problem consists in finding a single s–t path in an undirected graph and can be solved in Conn(V,E)=O(V+EVSort(V)loglogVBE) I/Os, where Sort(N)=O(NBlogM/BNB) is the complexity of sorting N words in external memory. Our contribution is two novel EM algorithms that solve the problem for k≤MB. The first takes O(k· Conn(V, E)) I/Os. The second one applies the ideas of Ibaraki–Nagamochi sparse connectivity certificates and takes O((Sort(V+E)+k·Conn(V,kV))·logVM) I/Os, which improves upon the first bound for sufficiently dense graphs. Both algorithms outperform the naive approach based on successive BFS- or DFS-augmentations for a wide range of parameters | V|, | E|, M, B. © 2018, Springer International Publishing AG.

Keywords: random access memory, problem solving, graph theory, Random access storage, Combinatorial problem, Disjoint paths, EM algorithms, External memory, External memory models, Undirected graph

In book

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Vol. 10706. , Springer, 2018.