Loukas Georgiadis

Prof. Dr. Loukas Georgiadis


Research Focus & Metrics

Academic Career Length

23Years (2004-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2006 in Journal of Graph Algorithms and Applications
Verified
Journal Article
Closed access
LGLoukas Georgiadis
Loukas Georgiadis
RTRobert E. Tarjan
Robert E. Tarjan
RWRenato F. Werneck
Renato F. Werneck

1 November 2013 in Journal of Discrete Algorithms
Verified
Journal Article
Closed access
WFWojciech Fraczak
Wojciech Fraczak
LGLoukas Georgiadis
Loukas Georgiadis
AMAndrew Miller
Andrew Miller
RTRobert E. Tarjan
Robert E. Tarjan

16 November 2015 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
LGLoukas Georgiadis
Loukas Georgiadis
RTRobert E. Tarjan
Robert E. Tarjan
How does one verify that the output of a complicated program is correct? One can formally prove that the program is correct, but this may be beyond the power of existing methods. Alternatively, one can check that the output produced for a particular input satisfies the desired input--output relation by running a checker on the input--output pair. Then one only needs to prove the correctness of the checker. For some problems, however, even such a checker may be too complicated to formally verify. There is a third alternative: augment the original program to produce not only an output but also a correctness certificate , with the property that a very simple program (whose correctness is easy to prove) can use the certificate to verify that the input--output pair satisfies the desired input--output relation. We consider the following important instance of this general question: How does one verify that the dominator tree of a flow graph is correct? Existing fast algorithms for finding dominators are complicated, and even verifying the correctness of a dominator tree in the absence of additional information seems complicated. We define a correctness certificate for a dominator tree, show how to use it to easily verify the correctness of the tree, and show how to augment fast dominator-finding algorithms so that they produce a correctness certificate. We also relate the dominator certificate problem to the problem of finding divergent spanning trees in a flow graph, and we develop algorithms to find such trees. All our algorithms run in linear time. Previous algorithms apply just to the special case of only trivial dominators, and they take at least quadratic time.

1 January 2020 in SIAM Journal on Computing
Verified
Journal Article
Closed access
LGLoukas Georgiadis
Loukas Georgiadis
GIGiuseppe F. Italiano
Giuseppe F. Italiano
NPNikos Parotsidis
Nikos Parotsidis
In this paper, we investigate some basic connectivity problems in directed graphs (digraphs). Let $G$ be a digraph with $m$ edges and $n$ vertices, and let $G\setminus e$ (resp., $G\setminus v$) be the digraph obtained after deleting edge $e$ (resp., vertex $v$) from $G$. As a first result, we show how to compute in $O(m+n)$ worst-case time: the total number of strongly connected components in $G\setminus e$ (resp., $G\setminus v$) for all edges $e$ (resp., for all vertices $v$) in $G$. Let $G$ be strongly connected. We say that edge $e$ (resp., vertex $v$) separates two vertices $x$ and $y$ if $x$ and $y$ are no longer strongly connected in $G\setminus e$ (resp., $G\setminus v$). As a second set of results, we show how to build in $O(m+n)$ time $O(n)$-space data structures that can answer in optimal time the following basic connectivity queries on digraphs: report in $O(n)$ worst-case time all the strongly connected components of $G\setminus e$ (resp., $G\setminus v$) for a query edge $e$ (resp., vertex $v$); test whether an edge or a vertex separates two query vertices in $O(1)$ worst-case time; report all edges (resp., vertices) that separate two query vertices in optimal worst-case time, i.e., in time $O(k)$, where $k$ is the number of separating edges (resp., separating vertices). (For $k=0$, the time is $O(1).$) All our bounds are tight and are obtained with a common algorithmic framework, based on a novel compact representation of the decompositions induced by the 1-connectivity (i.e., 1-edge and 1-vertex) cuts in digraphs, which might be of independent interest. With the help of our data structures we can design efficient algorithms for several other connectivity problems on digraphs and we can also obtain in linear time a strongly connected spanning subgraph of $G$ with $O(n)$ edges that maintains the 1-connectivity cuts of $G$ and the decompositions induced by those cuts.


10 October 2016 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
LGLoukas Georgiadis
Loukas Georgiadis
GIGiuseppe F. Italiano
Giuseppe F. Italiano
LLLuigi Laura
Luigi Laura
NPNikos Parotsidis
Nikos Parotsidis
Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly, not much has been investigated for directed graphs. In this article, we study 2-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices v and w are 2- edge-connected if there are two edge-disjoint paths from v to w and two edge-disjoint paths from w to v . This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the undirected case, those blocks do not correspond to the 2-edge-connected components of the graph. The main result of this article is an algorithm for computing the 2-edge-connected blocks of a directed graph in linear time. Besides being asymptotically optimal, our algorithm improves significantly over previous bounds. Once the 2-edge-connected blocks are available, we can test in constant time if two vertices are 2-edge-connected. Additionally, when two query vertices v and w are not 2-edge-connected, we can produce in constant time a “witness” of this property by exhibiting an edge that is contained in all paths from v to w or in all paths from w to v . We are also able to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has O ( n ) edges and maintains the same 2-edge-connected blocks as the input graph, where n is the number of vertices.