I/O-Efficient Algorithms for Graphs of Bounded Treewidth |
| |
Authors: | Anil Maheshwari Norbert Zeh |
| |
Affiliation: | (1) School of Computer Science, Carleton University, Ottawa, ON, K1S 5B6, Canada;(2) Faculty of Computer Science, Dalhousie University, Halifax, NS, B3H 2Y5, Canada |
| |
Abstract: | We present an algorithm that takes
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
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
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
I/Os.
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
I/Os. The maximal matching algorithm is used in the tree decomposition algorithm.
An abstract of this paper was presented at the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pp. 89–90,
2001.
Research of A. Maheshwari supported by NSERC.
Part of this work was done while the second author was a Ph.D. student at the School of Computer Science of Carleton University. |
| |
Keywords: | Algorithms External memory algorithms Bounded treewidth Graph algorithms |
本文献已被 SpringerLink 等数据库收录! |
|