A Labeling Approach to Incremental Cycle Detection
A Labeling Approach to Incremental Cycle Detection
复制标题
增量循环检测的标记方法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
L. Roditty
中科院分区：
文献类型：
--
作者：
E. Cohen;A. Fiat;Haim Kaplan;L. Roditty
在增量循环检测问题中，弧被添加到有向非循环图中，并且算法必须报告新弧是否关闭循环。人们寻求最小化处理整个弧插入序列的总时间，或者直到出现一个循环。
在最近的突破中，Bender，Fineman，吉尔伯特和Tarjan引用{BeFiGiTa 11}提出了两种不同的算法，其时间复杂度分别为O（n^2 log n）$和O（m cdot min {m^{1/2}，n^{2/3} }）$。
在本文中，我们介绍了一种新的技术，增量周期检测，使我们能够获得两个界限（对数因子）。此外，我们的方法似乎更友好的分布式实现。
In the emph{incremental cycle detection} problem arcs are added to a directed acyclic graph and the algorithm has to report if the new arc closes a cycle. One seeks to minimize the total time to process the entire sequence of arc insertions, or until a cycle appears.
In a recent breakthrough, Bender, Fineman, Gilbert and Tarjan cite{BeFiGiTa11} presented two different algorithms, with time complexity $O(n^2 log n)$ and $O(m cdot min {m^{1/2}, n^{2/3} })$, respectively.
In this paper we introduce a new technique for incremental cycle detection that allows us to obtain both bounds (up to a logarithmic factor). Furthermore, our approach seems more amiable for distributed implementation.