|
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
|
|
Alexandra Galani, Loukas Georgiadis, Stavros Nikolopoulos, Leonidas Palios |
|
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.
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.
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.
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)
Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs (ICALP 2011, Bordeaux)
Join-Reachability Problems in Directed Graphs (CSR 2011, St Petersburg) |
|
Contact |
|
Email: loukas@cs.uoi.gr
|
