Double DIKU Talk by Tarjan and Italiano – University of Copenhagen

Double DIKU Talk by Tarjan and Italiano

On 3 August 2017 DIKU hosts a double DIKU talk on algorithmic themes by Turing award winner and ACM Fellow Robert Tarjan and EATCS fellow Giuseppe Italiano. The talks are followed by a reception from 5 - 6 p.m. outside the Auditorium.

15.30 - 16.15 Concurrent Disjoint Set Union - Talk by Robert Tarjan

Robert Tarjan is a Turing award winner and elected ACM fellow. He is the inventor of fibonacci heaps and splay trees. He is currently a professor at Princeton University. (For more info: https://en.wikipedia.org/wiki/Robert_Tarjan).

Abstract

The disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is ongoing joint work with Siddhartha Jayanti.

16.15 - 17.00 2-Connectivity in Directed Graphs - Talk by Giuseppe Italiano

Giuseppe Italiano is an elected EATCS fellow, and received numerous awards. His research interests are in the design and analysis of algorithms for solving theoretical and applied problems in graphs, massive data sets and computer security. He is currently a professor at University of Rome Tor Vargata. (For more info: https://en.wikipedia.org/wiki/Giuseppe_F._Italiano)

Abstract

We survey some recent results on 2-edge and 2-vertex connectivity in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-connectivity has a much richer and more complicated structure. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by
simply using depth first search. In the case of digraphs, however, the very same problems have been much more challenging and have been tackled only recently.

The talks are followed by a reception.

Scientific host: Stephen Alstrup