Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
External Memory Algorithms for Finding Disjoint Paths in Undirected Graphs
verfasst von : Maxim Babenko, Ignat Kolesnichenko
Erschienen in: SOFSEM 2018: Theory and Practice of Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Consider the following well-known combinatorial problem: given an undirected graph \(G = (V,E)\), terminals \(s, t \in V\), and an integer \(k \ge 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\left( \frac{V+E}{V}\right. \left. Sort(V) \log \log \frac{VB}{E}\right) \) I/Os, where \(Sort(N) = O\left( \frac{N}{B}\log _{M/B} \frac{N}{B}\right) \) is the complexity of sorting N words in external memory.
Our contribution is two novel EM algorithms that solve the problem for \(k \le \frac{M}{B}\). The first takes \(O(k \cdot Conn(V,E))\) I/Os. The second one applies the ideas of Ibaraki–Nagamochi sparse connectivity certificates and takes \(O\left( (Sort(V+E) + k \cdot Conn(V,kV)) \cdot \log \frac{V}{M}\right) \) 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.