An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
复制标题
稀疏图中增量循环检测和拓扑排序的改进算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Janardhan Kulkarni
中科院分区：
文献类型：
--
作者：
Sayan Bhattacharya;Janardhan Kulkarni
我们考虑了有向图中的增量周期检测和拓扑排序的问题，$ g =（v，e）$ with $ | v | = n $节点。在这种情况下，最初是图形的边缘集$ e $是空的。随后，在每个时间阶段的边缘都将插入$ g $。在每个边缘插入之后，我们必须报告当前图是否包含一个周期，只要图形保持无环，我们就必须维护节点套件$ v $的拓扑排序。令$ m $为插入$ g $的边缘总数。我们使用$ \ tilde {o}（m^{4/3}）$呈现一个随机算法，以解决此问题。
We consider the problem of incremental cycle detection and topological ordering in a directed graph $G = (V, E)$ with $|V| = n$ nodes. In this setting, initially the edge-set $E$ of the graph is empty. Subsequently, at each time-step an edge gets inserted into $G$. After every edge-insertion, we have to report if the current graph contains a cycle, and as long as the graph remains acyclic, we have to maintain a topological ordering of the node-set $V$. Let $m$ be the total number of edges that get inserted into $G$. We present a randomized algorithm for this problem with $\tilde{O}(m^{4/3})$ total expected update time.