Uma nova abordagem para detecção de ciclo incremental
Resumo
O problema de detecção de ciclo incremental consiste em, dado um grafo direcionado (inicialmente vazio) tal que as arestas são adicionadas uma a uma, detectar quando um ciclo é formado. Recentemente, dois artigos foram apresentados sobre o assunto [1, 2].[...]Downloads
Referências
Michael A. Bender et al. _A New Approach to Incremental Cycle Detection and Related Problems_. Em: ACM Trans. Algorithms 12.2 (dez. de 2015), 14:1_14:22. doi: 10.1145/2756553.
Aaron Bernstein e Shiri Chechik. _Incremental Topological Sort and Cycle Detection in Õ(mpn) Expected Total Time_. Em: Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2018, pp. 21_34. doi: 10.1137/1.9781611975031.2.
Aric Hagberg, Daniel A. Schult e Pieter Jacob Swart. _Exploring Network Structure, Dynamics, and Function using NetworkX_. Em: Proceedings of the 7th Python in Science Conference. Ed. por Gaël Varoquaux, Travis Vaught e Jarrod Millman. Pasadena, CA USA, 2008, pp. 11 _15.
Jérôme Kunegis. _KONECT: The Koblenz Network Collection_. Em: Proceedings of the 22nd International Conference on World Wide Web. WWW '13 Companion. Rio de Janeiro, Brazil: Association for Computing Machinery, 2013, 1343_1350. isbn: 9781450320382. doi: 10.1145/2487788.2488173.
E.F. Moore. _The shortest path through a maze_. Em: International Symposium on the Theory of Switching. Harvard University Press, 1959, pp. 285_292.
Robert E. Tarjan. _Depth-First Search and Linear Graph Algorithms_. Em: SIAM Journal on Computing 1.2 (1972), pp. 146_160. doi: 10.1137/0201010.
