Depth First Search in the Semi-streaming Model
Depth First Search in the Semi-streaming Model
复制标题
半流式模型中的深度优先搜索
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shashank K. Mehta
中科院分区：
文献类型：
--
作者：
Shahbaz Khan;Shashank K. Mehta
深度优先搜索（DFS）树是解决各种图问题的基本数据结构。对于具有 $n$ 个顶点和 $m$ 个边的图，经典 DFS 算法需要 $O(m+n)$ 时间。在流模型中，允许算法对输入图进行多次传递（最好是单次传递），并对所使用的局部空间的大小有限制。
简单地说，可以使用 $O(m)$ 空间通过单次计算来计算 DFS 树。在允许 $O(n)$ 空间的半流模型中，它可以在 $O(n)$ 遍中计算，其中每一遍向 DFS 树添加一个顶点。然而，即使在任何宽松的流环境中，使用 $o(n)$ 传递和 $o(m)$ 空间来计算 DFS 树仍然是一个悬而未决的问题。
我们提出了第一个半流算法，该算法使用 $o(m)$ 空间在 $o(n)$ 遍中计算无向图的 DFS 树。我们首先描述一个极其简单的算法，最多需要 $lceil n/k
ceil$ 使用 $O(nk)$ 空间传递，其中 $k$ 是任何正整数。然后，我们通过使用更多复杂的技术来改进该算法，将传递次数减少到 $lceil h/k
ceil$ 在类似的空间约束下，其中 $h$ 是计算的 DFS 树的高度。特别是，该算法改进了计算的 DFS 树较浅（具有 $o(n)$ 高度）的情况的边界。此外，该算法作为一个框架提出，允许灵活地使用任何算法将存储的稀疏子图的 DFS 树维护为黑匣子，这可能是独立的兴趣。这两种算法本质上都证明了计算 DFS 树所需的空间和遍数之间存在权衡。此外，我们通过实验评估这些算法，揭示了它们在实践中的卓越性能。对于随机图和真实图，即使只允许 $O(n)$ 空间，它们也只需要几次传递。
Depth first search (DFS) tree is a fundamental data structure for solving various graph problems. The classical DFS algorithm requires $O(m+n)$ time for a graph having $n$ vertices and $m$ edges. In the streaming model, an algorithm is allowed several passes (preferably single) over the input graph having a restriction on the size of local space used.
Trivially, a DFS tree can be computed using a single pass using $O(m)$ space. In the semi-streaming model allowing $O(n)$ space, it can be computed in $O(n)$ passes, where each pass adds one vertex to the DFS tree. However, it remains an open problem to compute a DFS tree using $o(n)$ passes using $o(m)$ space even in any relaxed streaming environment.
We present the first semi-streaming algorithms that compute a DFS tree of an undirected graph in $o(n)$ passes using $o(m)$ space. We first describe an extremely simple algorithm that requires at most $lceil n/k
ceil$ passes using $O(nk)$ space, where $k$ is any positive integer. We then improve this algorithm by using more involved techniques to reduce the number of passes to $lceil h/k
ceil$ under similar space constraints, where $h$ is the height of the computed DFS tree. In particular, this algorithm improves the bounds for the case where the computed DFS tree is shallow (having $o(n)$ height). Moreover, this algorithm is presented as a framework that allows the flexibility of using any algorithm to maintain a DFS tree of a stored sparser subgraph as a black box, which may be of independent interest. Both these algorithms essentially demonstrate the existence of a trade-off between the space and number of passes required for computing a DFS tree. Furthermore, we evaluate these algorithms experimentally which reveals their exceptional performance in practice. For both random and real graphs, they require merely a few passes even when allowed just $O(n)$ space.
图形流上两次、三次以及更多次的最大匹配
DOI：
10.4230/lipics.approx-random.2017.15
发表时间：
2017
期刊：
and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Kale, Sagar;Tirodkar, Sumedh
通讯作者：
Tirodkar, Sumedh