Uma nova abordagem para detecção de ciclo incremental

João Victor P. de Almeida, Danilo Artigas

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].[...]

Texto completo:

PDF

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.


Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato