We present an algorithm that takes ON I/Os (sort(N)=Θ((N/(DB)) log∈ M/B (N/B)) is the number of I/Os it takes to sort N data items) to compute a tree decomposition of width at most k, for any graph G of treewidth at most k and size N, where k is a constant. Given such a tree decomposition, we use a dynamic programming framework to solve a wide variety of problems on G in ON DB I/Os, including the single-source shortest path problem and a number of problems that are NP-hard on general graphs. The tree decomposition can also be used to obtain an optimal separator decomposition of G. We use such a decomposition to perform depth-first search in G in ON DB I/Os. As important tools that are used in the tree decomposition algorithm, we introduce flippable DAGs and present an algorithm that computes a perfect elimination ordering of a k-tree in ON. The second contribution of our paper, which is of independent interest, is a general and simple framework for obtaining I/O-efficient algorithms for a number of graph problems that can be solved using greedy algorithms in internal memory. We apply this framework in order to obtain an improved algorithm for finding a maximal matching and the first deterministic I/O-efficient algorithm for finding a maximal independent set of an arbitrary graph. Both algorithms take O. The maximal matching algorithm is used in the tree decomposition algorithm.

Additional Metadata
Keywords Algorithms, Bounded treewidth, External memory algorithms, Graph algorithms
Persistent URL dx.doi.org/10.1007/s00453-007-9131-5
Journal Algorithmica
Maheshwari, A, & Zeh, N. (Norbert). (2009). I/O-Efficient Algorithms for Graphs of Bounded Treewidth. Algorithmica, 54(3), 413–469. doi:10.1007/s00453-007-9131-5