I/O-Efficient Algorithms for Bounded Treewidth Graphs
I/O-Efficient Algorithms for Bounded Treewidth Graphs
复制标题
有界树宽图的 I/O 高效算法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
N. Zeh
中科院分区：
文献类型：
--
作者：
A. Maheshwari;N. Zeh
针对有界树宽图的单源最短路径问题，提出了一种I/O高效算法。对于一般的稀疏图，SSSP似乎非常难以解决。我们展示了如何解决SSSP在O排序N I/O为上述类别的图。我们的解决方案的一个重要组成部分是O排序N算法来计算给定图的宽度k的树分解。给定这种分解，求解SSSP的算法相当简单。为了构建树组合，我们提出了一个I/O高效的算法，找到一个图的最大匹配，并引入可翻转的DAG作为一个有趣的新概念，可能是有用的其他应用程序以及。我们还展示了如何实现著名的时间向前处理技术在O扫描N I/O，如果处理的图形是一棵树，其顶点排序在前序。这并没有给出任何渐近改进，但从实用的角度来看是有趣的，因为所使用的技术非常简单。
We present an I/O-efficient algorithm for the single source shortest path (SSSP) problem for graphs of bounded treewidth. For sparse graphs in general SSSP seems to be extremely hard to solve. We show how to solve SSSP in O sort N I/Os for the above class of graphs. An important ingredient to our solution is an O sort N algorithm to compute a tree-decomposition of width k of the given graph. Given this decomposition, the algorithm for solving SSSP is rather simple. In order to construct the treedecomposition, we present an I/O-efficient algorithm for finding a maximal matching of a graph, and introduce flippable DAGs as an interesting new concept that may be useful for other applications as well. We also show how to realize the well-known time-forward processing technique in O scan N I/Os if the processed graph is a tree whose vertices are sorted in preorder. This does not give any asymptotic improvements, but is interesting from a practical point of view, as the used techniques are extremely simple.