External memory algorithms for finding disjoint paths in undirected graphs(

P. 295–304.

Бабенко М. А., Колесниченко И. И.

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.

Ключевые слова: random access memory, problem solving, graph theory, Random access storage, Combinatorial problem, Disjoint paths, EM algorithms, External memory, External memory models, Undirected graph

В книге

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

Vol. 10706. , Springer, 2018.