Efficient Algorithms for Reachability and PathSelection Problems with Applications
Project funded by The John S. Latsis Public Benefit Foundation

Project Description
The objective of this project is the design of efficient algorithms for a collection of graph problems related to Reachability and PathSelection. In these problems we are given an input graph and wish to efficiently perform queries that report if two vertices are connected or compute paths connecting specified vertices so that certain requirements are satisfied. These algorithmic primitives have numerous and diverse applications in areas such as Internet Routing, Geographical Navigation, Semantic Web, and Social Networks. Motivated by recent advances in these areas we study novel variants of Reachability and PathSelection problems. Furthermore, we develop new applications of these problems in other areas such as Language Processing. 
Team Members

Alexandra Galani, Loukas Georgiadis, Stavros Nikolopoulos, Leonidas Palios 
Papers 
Presentations 
L. Georgiadis, “Testing 2Vertex Connectivity and Computing Pairs of VertexDisjoint st Paths in Digraphs”. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) Track A, pages 738749.
L. Georgiadis, S. D. Nikolopoulos, and L. Palios, “JoinReachability Problems in Directed Graphs”. 6th International Computer Science Symposium in Russia (CSR 2011), pages 195208. Full version in Theory of Computing Systems, volume 55(2), pages 347379, 2014. Special Issue on Selected Papers from CSR 2011.
L. Georgiadis, “Approximating the Smallest 2Vertex Connected Spanning Subgraph of a Directed Graph”. In Proceedings of the19th Annual European Symposium on Algorithms (ESA 2011), pages 1324.
L. Georgiadis and R. E. Tarjan, “Dominators, Directed Bipolar Orders, and Independent Spanning Trees”. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012) Track A, pages 375386 . 
Project Overview Project Overview (J. S. Latsis Foundation, May 2011)
Testing 2Vertex Connectivity and Computing Pairs of VertexDisjoint st Paths in Digraphs (ICALP 2011, Bordeaux)
JoinReachability Problems in Directed Graphs (CSR 2011, St Petersburg) 
Contact 
Email: loukas@cs.uoi.gr
