Submitted

 

Incremental Strong Connectivity and 2-Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis

 

 

Conference Papers

 

Computing 2-Connected Components and Maximal 2-Connected Subgraphs in Directed Graphs: An Experimental Study

Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou, Nikos Parotsidis and Nilakantha Paudel

In Proceedings of the 20th SIAM Meeting on Algorithm Engineering and Experimentation (ALENEX 2018). To appear.

 

Decremental Data Structures for Connectivity and Dominators in Directed Graphs

Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger and Nikos Parotsidis

In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) A, pages 42:1--42:15.

Preliminary full version at arXiv

 

All-Pairs 2-Reachability in O(nlogn) Time

Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis and Przemysław Uznański

In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) A, pages 74:1--74:14.

Preliminary version at arXiv

 

Incremental Low-High Orders of Directed Graphs and Applications

Loukas Georgiadis, Konstantinos Giannis, Aikaterini Karanasiou and Luigi Laura 

In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), pages 27:1-27:21.

Preliminary version at arXiv

 

Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Orders

Loukas Georgiadis, Giuseppe F. Italiano and Aikaterini Karanasiou

In Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), pages 9:1-9:16.

 

Strong Connectivity in Directed Graphs under Failures, with Applications

Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis

In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 1880-1899.

Preliminary full version at arXiv

 

Computing Critical Nodes in Directed Graphs

Nilakantha Paudel, Loukas Georgiadis and Giuseppe F. Italiano

In Proceedings of the 19th SIAM Meeting on Algorithm Engineering and Experimentation (ALENEX 2017), pages 43-57.

 

2-Connectivity in Directed Graphs (G. F. Italianos invited talk, ESA 2016)

Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis 

In Proceedings of the 24th Annual European Symposium on Algorithms (ESA 2016), pages 1:1-1:14.

 

Incremental 2-Edge-Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis 

In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) A, pages 49:1-49:15.

Preliminary full version at arXiv

 

Sparse Subgraphs for 2-Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou, Charis Papadopoulos and Nikos Parotsidis

In Proceedings of the 15th International Symposium on Experimental Algorithms (SEA 2016), pages 150-166.

 

Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano, Charis Papadopoulos and Nikos Parotsidis

In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA 2015) B, pages 582-594.

Full version at arXiv

 

2-Vertex Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura and Nikos Parotsidis

In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) A, pages 605-616.

Preliminary version at arXiv

 

2-Connectivity in Directed Graphs: An Experimental Study

William Di Luigi, Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura and Nikos Parotsidis

In Proceedings of the 17th SIAM Meeting on Algorithm Engineering and Experimentation (ALENEX 2015), pages 173-187.

 

2-Edge Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura and Nikos Parotsidis

In Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 1988-2005.

Preliminary version at arXiv

 

Loop Nesting Forests, Dominators, and Applications

Loukas Georgiadis, Luigi Laura, Nikos Parotsidis and Robert E. Tarjan

In Proceedings of the 13th International Symposium on Experimental Algorithms (SEA 2014), pages 174-186.

 

Dominator Tree Certification and Independent Spanning Trees: An Experimental Study

Loukas Georgiadis, Luigi Laura, Nikos Parotsidis and Robert E. Tarjan

In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA 2013), pages 284-295.

 

Dominators in Directed Graphs: A Survey of Recent Results, Applications, and Open Problems

Loukas Georgiadis and Nikos Parotsidis

Proceedings of the 2nd International Symposium on Computing in Informatics and Mathematics (ISCIM 2013), pages 15-20.

 

An Experimental Study of Dynamic Dominators

Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura and Federico Santaroni

In Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012) B, pages 491-502.

Preliminary full version at arXiv

 

Dominators, Directed Bipolar Orders, and Independent Spanning Trees

Loukas Georgiadis and Robert E. Tarjan

In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012) A, pages 375-386.     

 

Approximating the Smallest 2-Vertex Connected Spanning Subgraph of a Directed Graph

Loukas Georgiadis

In Proceedings of the19th Annual European Symposium on Algorithms (ESA 2011) B, pages 13-24.

Preliminary version

 

Dynamic Dominators in Practice

Konstantinos Patakakis, Loukas Georgiadis, and Vasileios A. Tatsis.

In Proceedings of the 15th Panhellenic Conference on Informatics (PCI 2011), pages 100-104.

 

Join-Reachability Problems in Directed Graphs

Loukas Georgiadis, Stavros D. Nikolopoulos, and Leonidas Palios

In Proceedings of the 6th International Computer Science Symposium in Russia (CSR 2011), pages 195-208.

Preliminary version

 

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

Loukas Georgiadis

In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) A, pages 738-749.

Preliminary version

 

An Experimental Study of Minimum Mean Cycle Algorithms
Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, and Renato F. Werneck

In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX 2009), pages1-13.

SIAM.

 

Computing Frequency Dominators and Related Problems
Loukas Georgiadis

In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC 2008), pages 704-715.

Springer-Verlag.

Preliminary version

        

Shortest Path Feasibility Algorithms: An Experimental Evaluation
Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan and Renato F. Werneck

In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX 2008), pages 118-132.

SIAM.


Dynamic Matchings in Convex Bipartite Graphs
Gerth S. Brodal, Loukas Georgiadis, Kristoffer A. Hansen and Irit Katriel
In Proceedings of the 32nd International Symposium on Mathematical Fundations of Computer Science (MFCS 2007),
Lecture Notes in Computer Science, volume 4708, pages 406-417, Springer-Verlag, 2007.
Springer-Verlag.

Improved Dynamic Planar Point Location
Lars Arge, Gerth S. Brodal and Loukas Georgiadis
In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS 2006), pages 305-314.
IEEE.

Preliminary version

        
Design of Data Structures for Mergeable Trees
Loukas Georgiadis, Robert E. Tarjan and Renato F. Werneck
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pages 394-403, 2006.
SIAM.

Preliminary version

 

Dominator Tree Verification and Vertex-Disjoint Paths
Loukas Georgiadis and Robert E. Tarjan
In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 433-442, 2005.
SIAM.

Preliminary version

 

Finding Dominators in Practice
Loukas Georgiadis, Renato F. Werneck, Robert E. Tarjan, Spyridon Triantafyllis and David I. August
In Proceedings of the 12th Annual European Symposium on Algorithms (ESA 2004) B,
Lecture Notes in Computer Science, volume 3221, pages 677-688, Springer-Verlag, 2004.
Springer-Verlag.

Preliminary version

 

Finding Dominators Revisited
Loukas Georgiadis and Robert E. Tarjan
In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pages 862-871, 2004.
SIAM.

Preliminary version

       

 

       

Journal Papers

 

Sparse Certificates for 2-Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou, Charis Papadopoulos and Nikos Parotsidis

Theoretical Computer Science.

 

2-Edge Connectivity in Directed Graphs

Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura and Nikos Parotsidis

ACM Transactions on Algorithms, volume 13, issue 1, pages 9:1-9:24, October 2016.

 

Addendum to Dominator Tree Certification and Divergent Spanning Trees

(A Note on Fault Tolerant Reachability for Directed Graphs)

Loukas Georgiadis and Robert E. Tarjan

ACM Transactions on Algorithms, volume 12, issue 4, pages 56:1-56:3, August 2016.

Preliminary version at arXiv

 

Dominator Tree Certification and Divergent Spanning Trees

Loukas Georgiadis and Robert E. Tarjan

ACM Transactions on Algorithms, volume 12, issue 1, pages 11:1-11:42, November 2015.

Preliminary version at arXiv

 

Strong Articulation Points and Strong Bridges in Large Scale Graphs

Donatella Firmani, Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni

Algorithmica, volume 74, number 3, pages 1123-1147.

Springer.

 

Join-Reachability Problems in Directed Graphs

Loukas Georgiadis, Stavros D. Nikolopoulos, and Leonidas Palios

Theory of Computing Systems, volume 55(2), pages 347-379, 2014.

Special Issue on Selected Papers from CSR 2011.

Springer.

 

Corrections to Finding Dominators via Disjoint Set Union

Wojciech Fraczak, Loukas Georgiadis, Andrew Miller, and Robert E. Tarjan

Journal of Discrete Algorithms (JDA), volume 26, pages 106-110, 2014.

Elsevier.

 

Finding Dominators via Disjoint Set Union

Wojciech Fraczak, Loukas Georgiadis, Andrew Miller, and Robert E. Tarjan

Journal of Discrete Algorithms (JDA), volume 23, pages 2-20, 2013.

Elsevier.

Preliminary version at arXiv

 

Data Structures for Mergeable Trees
Loukas Georgiadis, Haim Kaplan, Nira Shafrir, Robert E. Tarjan and Renato Werneck

ACM Transactions on Algorithms, volume 7, issue 2, pages 14:1-14:30, 2011.

ACM.

Preliminary version at arXiv

 

Shortest Path Feasibility Algorithms: An Experimental Evaluation
Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan and Renato F. Werneck

ACM Journal of Experimental Algorithmics, special section devoted to selected best papers
presented at ALENEX'08, volume 14, pages 2.7-2.47, 2009.

ACM.

 

Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
 Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Ann Rogers, Robert E. Tarjan and Jeffery R. Westbrook

SIAM Journal on Computing, volume 38, issue 4, pages 1533-1573, 2008.

SIAM.

Preliminary version at arXiv

       

An O(nlogn) Version of the Averbakh-Berman Algorithm for the Robust Median of a Tree
Gerth S. Brodal, Loukas Georgiadis, and Irit Katriel

Operations Research Letters, volume 36, issue 1, pages 14-18.

Elsevier.

Preliminary version


Finding Dominators in Practice
Loukas Georgiadis, Robert E. Tarjan and Renato F. Werneck
Journal of Graph Algorithms and Applications (JGAA), volume 10, issue 1, pages 69-94.
Special Issue on Selected Papers from Engineering and Applications Track of ESA 2004.


 

Books

 

Data Structures (in Greek)

Loukas Georgiadis, Stavros D. Nikolopoulos and Leonidas Palios

Kallipos 2015

 

Algorithmic Graph Theory (in Greek)

Stavros D. Nikolopoulos, Leonidas Palios and Loukas Georgiadis

Kallipos 2015

 

Wireless Network Traffic and Quality of Service Support: Trends and Standards

T. D. Lagkas, P. Angelidis and L. Georgiadis (Editors)

IGI Global, 2010.

 

 

 

PhD Thesis

 

Linear-Time Algorithms for Dominators and Related Problems

Princeton Department of Computer Science TR-737-05, Princeton University, 2005.

 

Publications

Activities

Teaching

+30 26510 08914

loukas@cs.uoi.gr

telephone

email

Loukas Georgiadis
Assistant Professor

 

Department of Computer Science & Engineering

University of Ioannina