Seminar in Algorithms 89-436

Papers List

Papers

 

Franciosa, P.G., Gambosi, G., Nanni, U.: The incremental maintenance of a depth-first-search tree in directed acyclic graphs. Inf. Process. Lett. 61(2), 1997. 

Speaker: Roy Shefi.

Date: 14/3/2018

 

Surender Baswana and Shahbaz Khan: Incremental algorithm for DFS tree in undirected graphs. Algorithmica 79(2), 466-483, 2017.

Speaker: Gilad Segal

Date: 28/3/2018

 

Surender Baswana, Keerti Choudhary: On Dynamic DFS Tree in Directed Graphs. MFCS (2) 2015: 102-114.

Speaker: Haim Vitman

Date: 11/04/2018

 

Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, Shahbaz Khan: Dynamic DFS in Undirected Graphs: breaking the O(m) barrier. SODA 2016: 730-739

Speaker: Dimitry Shekalovsi

Date: 25/04/2018

Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang: Improved Algorithms for Maintaining DFS Tree in Undirected Graphs. CoRR abs/1607.04913 (2016)

Speaker: Yuval Zanani Levi

Date: 2/05/2018

Surender Baswana, Ayush Goel, Shahbaz Khan: Incremental DFS algorithms: a theoretical and experimental study. SODA 2018: 53-72

Speaker: Michael Itzaki

Date: 9/5/2018

Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis: Strong Connectivity in Directed Graphs under Failures, with Applications. SODA 2017: 1880-1899

 

Speaker: Roni Jacobi

Date: 16/5/2018

 

John H. Reif: A topological approach to dynamic graph connectivity. IPL 1987.

John H. Reif: Depth-first search is inherently sequential. IPL 1985.

 

Speaker: Itai Bone.

Date: 23/5/2018

 

 

Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan: Incremental Cycle Detection, Topological Ordering, and Strong

Component Maintenance. ACM Trans. Algorithms 8(1): 3:1-3:33 (2012)

Speaker:

Date:

 

Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Robert E. Tarjan:

A New Approach to Incremental Cycle Detection and Related Problems. ACM Trans. Algorithms 12(2): 14:1-14:22 (2016)

Speaker:

Date:

 

Aaron Bernstein, Shiri Chechik: Incremental Topological Sort and Cycle Detection in Expected Total Time. SODA 2018: 21-34

Speaker:

Date: