• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

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.

In book

Edited by: J. Wiedermann, A. Tjoa, S. Biffl et al. Vol. 10706. Springer, 2018.