Efficient Algorithms for Reachability

and Path-Selection 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 Path-Selection. 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 Path-Selection problems. Furthermore, we develop new applications of these problems in other areas such as Language Processing.

Team Members

 

 

Papers

Presentations

L. Georgiadis, Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) Track A, pages 738-749.

Preliminary version

 

 

L. Georgiadis, S. D. Nikolopoulos, and L. Palios, Join-Reachability Problems in Directed Graphs. 6th International Computer Science Symposium in Russia (CSR 2011),  pages 195-208. Full version in Theory of Computing Systems, volume 55(2), pages 347-379, 2014. Special Issue on Selected Papers from CSR 2011.

Preliminary version     

 

 

L. Georgiadis, Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph.  In Proceedings of the19th Annual European Symposium on Algorithms (ESA 2011), pages 13-24.

Preliminary version

 

 

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 375-386 .

Project Overview Project Overview (J. S. Latsis Foundation, May 2011)

PDF slides

 

 

Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs

(ICALP 2011, Bordeaux)

PDF slides

  

Join-Reachability Problems in Directed Graphs (CSR 2011, St Petersburg)

PDF slides

Contact

Email: loukas@cs.uoi.gr