BARC talk by Nikos Parotsidis

Friday, 1 February,  our new colleague Nikos Parotsidis joins BARC and AC section and will give a talk "Connectivity in directed Graphs: static, fault-tolerant, and dynamic"

Titel

Connectivity in directed Graphs: static, fault-tolerant, and dynamic

Abstract

The study of graphs is one of the classic areas of computer science and it is motivated mainly by the ability of graphs to model complex relations between entities. For instance, graphs can model the Web, social networks, road networks, biological networks, and many more. Connectivity-related concepts play a central role in graph theory as they provide fundamental tools for the analysis, processing, and understanding of graphs, and subsequently of the complex relations that they represent. Thus, it is not surprising, that connectivity-related concepts have been studied for several decades, mainly in undirected graphs. However, our understanding of many connectivity notions remains limited, especially in directed graphs.

In this talk, we review recent developments of algorithms for basic connectivity notions in directed graphs. In particular, we discuss several results in three different settings: the static setting, the fault-tolerant setting, and the dynamic setting. First, we present recent algorithms for computing 2-connectivity notions in directed graphs. For undirected graphs, we know how to solve those problems in asymptotically optimal time for over 45 years. However, only recently efficient algorithms have been discovered in directed graphs. Apart from those algorithms being theoretically efficient, we also show that their careful implementation allows them to become practical for processing large real-world graphs. Second, we review some results of data structures that can answer efficiently several basic connectivity queries in directed graphs under edge or vertex failures. Specifically, we discuss data structures that can answer various reachability and strong connectivity queries in the presence of edge or vertex failures. Finally, we review recent algorithms for maintaining basic connectivity notions in directed graphs whose structure is changing dynamically.

More about Nikos Parotsidis