Vertex Ordering Problems in Directed Graph Streams
Vertex Ordering Problems in Directed Graph Streams
复制标题
有向图流中的顶点排序问题
DOI：
10.1137/1.9781611975994.109
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vorotnikova, Sofya
中科院分区：
文献类型：
--
作者：
Chakrabarti, Amit;Ghosh, Prantar;McGregor, Andrew;Vorotnikova, Sofya
我们考虑了流设置中的有向图算法，重点关注有关顶点排序的问题。这包括拓扑排序和不环性测试等基本问题。我们还研究了寻找最小反馈弧集（其移除产生无环图的边）和寻找汇聚顶点的相关问题。我们对对抗有序流和随机有序流都感兴趣。对于任意输入图，我们证明了大多数这些问题具有很高的空间复杂性，排除了亚线性空间的解决方案。当流是随机排序的时候，一些下界也适用：例如，在我们最技术性的结果中，我们表明在p-pass随机顺序模型中测试非循环性大约需要n1+1/pspace。对于其他问题，随机排序可以产生巨大的差异：例如，在使用polylog(n)空间的一次性随机顺序模型中，有可能在无循环锦标赛中找到一个sink，而在对抗性排序中，假设Θ(p)通过，大约n1/pspace是必要和充分的。我们还设计了对抗赛图中反馈弧集问题的次线性算法；对于随机图；对于随机排序的流。在某些情况下，我们给出下界来证明我们的算法本质上是空间最优的。总之，我们的结果补充了在无向图流算法方面更为成熟的工作。
We considerdirectedgraph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sorting and acyclicity testing. We also study the related problems of finding a minimum feedback arc set (edges whose removal yields an acyclic graph), and finding a sink vertex. We are interested in both adversarially-ordered and randomly-ordered streams. For arbitrary input graphs with edges ordered adversarially, we show that most of these problems have high space complexity, precluding sublinear-space solutions. Some lower bounds also apply when the stream is randomly ordered: e.g., in our most technical result we show that testing acyclicity in thep-pass random-order model requires roughlyn1+1/pspace. For other problems, random ordering can make a dramatic difference: e.g., it is possible to find a sink in an acyclic tournament in the onepass random-order model using polylog(n) space whereas under adversarial ordering roughlyn1/pspace is necessary and sufficient given Θ(p) passes. We also design sublinear algorithms for the feedback arc set problem in tournament graphs; for random graphs; and for randomly ordered streams. In some cases, we give lower bounds establishing that our algorithms are essentially space-optimal. Together, our results complement the much maturer body of work on algorithms forundirectedgraph streams.
登录
查看更多内容
DOI：
10.1145/3087556.3087585
发表时间：
2016
期刊：
Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
M. Bateni;Hossein Esfandiari;V. Mirrokni
通讯作者：
V. Mirrokni
在流模型中模拟图上的随机游走
影响因子：
4.4
作者：
Ce Jin
通讯作者：
Ce Jin
DOI：
10.1145/1374376.1374470
发表时间：
2008
期刊：
Proceedings of the fortieth annual ACM symposium on Theory of computing
影响因子：
--
作者：
Amit Chakrabarti;Graham Cormode;A. Mcgregor
通讯作者：
A. Mcgregor
具有随机成本的排序和选择
DOI：
--
发表时间：
2007
期刊：
Latin American Symposium on Theoretical Informatics
影响因子：
--
作者：
Stanislav Angelov;K. Kunal;A. Mcgregor
通讯作者：
A. Mcgregor
半流式模型中的深度优先搜索
DOI：
--
发表时间：
2019
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Shahbaz Khan;Shashank K. Mehta
通讯作者：
Shashank K. Mehta