Source author record

Loukas Georgiadis

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

10works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems

A directed graph $G=(V,E)$ is twinless strongly connected if it contains a strongly connected spanning subgraph without any pair of antiparallel (or twin) edges. The twinless strongly connected components (TSCCs) of a directed graph $G$ are its maximal twinless strongly connected subgraphs. These concepts have several diverse applications, such as the design of telecommunication networks and the structural stability of buildings. A vertex $v \in V$ is a twinless strong articulation point of $G$ if the deletion of $v$ increases the number of TSCCs of $G$ . Here, we present the first linear-time algorithm that finds all the twinless strong articulation points of a directed graph. We show that the computation of twinless strong articulation points reduces to the following problem in undirected graphs, which may be of independent interest: Given a $2$ -vertex-connected (biconnected) undirected graph $H$ , find all vertices $v$ that belong to a vertex-edge cut-pair, i.e., for which there exists an edge $e$ such that $H \setminus \{v,e\}$ is not connected. We develop a linear-time algorithm that not only finds all such vertices $v$ , but also computes the number of edges $e$ such that $H \setminus \{v,e\}$ is not connected. This also implies that for each twinless strong articulation point $v$ which is not a strong articulation point in a strongly connected digraph $G$ , we can compute the number of TSCCs in $G \setminus v$ . We note that the problem of computing all vertices that belong to a vertex-edge cut-pair can be solved in linear-time by exploiting the structure of $3$ -vertex-connected (triconnected) components of $H$ , represented by an SPQR tree of $H$ . Our approach, however, is conceptually simple, and thus likely to be more amenable to practical implementations.

preprint2016arXiv

An Experimental Study of Dynamic Dominators

Motivated by recent applications of dominator computations, we consider the problem of dynamically maintaining the dominators of flow graphs through a sequence of insertions and deletions of edges. Our main theoretical contribution is a simple incremental algorithm that maintains the dominator tree of a flow graph with $n$ vertices through a sequence of $k$ edge insertions in $O(m\min\{n,k\}+kn)$ time, where $m$ is the total number of edges after all insertions. Moreover, we can test in constant time if a vertex $u$ dominates a vertex $v$ , for any pair of query vertices $u$ and $v$ . Next, we present a new decremental algorithm to update a dominator tree through a sequence of edge deletions. Although our new decremental algorithm is not asymptotically faster than repeated applications of a static algorithm, i.e., it runs in $O(mk)$ time for $k$ edge deletions, it performs well in practice. By combining our new incremental and decremental algorithms we obtain a fully dynamic algorithm that maintains the dominator tree through intermixed sequence of insertions and deletions of edges. Finally, we present efficient implementations of our new algorithms as well as of existing algorithms, and conduct an extensive experimental study on real-world graphs taken from a variety of application areas.

preprint2016arXiv

Incremental $2$ -Edge-Connectivity in Directed Graphs

In this paper, we initiate the study of the dynamic maintenance of $2$ -edge-connectivity relationships in directed graphs. We present an algorithm that can update the $2$ -edge-connected blocks of a directed graph with $n$ vertices through a sequence of $m$ edge insertions in a total of $O(mn)$ time. After each insertion, we can answer the following queries in asymptotically optimal time: (i) Test in constant time if two query vertices $v$ and $w$ are $2$ -edge-connected. Moreover, if $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$ . (ii) Report in $O(n)$ time all the $2$ -edge-connected blocks of $G$ . To the best of our knowledge, this is the first dynamic algorithm for $2$ -connectivity problems on directed graphs, and it matches the best known bounds for simpler problems, such as incremental transitive closure.

preprint2016arXiv

On Low-High Orders of Directed Graphs: Incremental Algorithms and Applications

A flow graph $G=(V,E,s)$ is a directed graph with a distinguished start vertex $s$ . The dominator tree $D$ of $G$ is a tree rooted at $s$ , such that a vertex $v$ is an ancestor of a vertex $w$ if and only if all paths from $s$ to $w$ include $v$ . The dominator tree is a central tool in program optimization and code generation and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low-high order of $G$ is a preorder $δ$ of $D$ that certifies the correctness of $D$ and has further applications in connectivity and path-determination problems. In this paper, we first consider how to maintain efficiently a low-high order of a flow graph incrementally under edge insertions. We present algorithms that run in $O(mn)$ total time for a sequence of $m$ edge insertions in an initially empty flow graph with $n$ vertices.These immediately provide the first incremental certifying algorithms for maintaining the dominator tree in $O(mn)$ total time, and also imply incremental algorithms for other problems. Hence, we provide a substantial improvement over the $O(m^2)$ simple-minded algorithms, which recompute the solution from scratch after each edge insertion. We also show how to apply low-high orders to obtain a linear-time $2$ -approximation algorithm for the smallest $2$ -vertex-connected spanning subgraph problem (2VCSS). Finally, we present efficient implementations of our new algorithms for the incremental low-high and 2VCSS problems and conduct an extensive experimental study on real-world graphs taken from a variety of application areas. The experimental results show that our algorithms perform very well in practice.

preprint2015arXiv

A Note on Fault Tolerant Reachability for Directed Graphs

In this note we describe an application of low-high orders in fault-tolerant network design. Baswana et al. [DISC 2015] study the following reachability problem. We are given a flow graph $G = (V, A)$ with start vertex $s$ , and a spanning tree $T =(V, A_T)$ rooted at $s$ . We call a set of arcs $A'$ valid if the subgraph $G' = (V, A_T \cup A')$ of $G$ has the same dominators as $G$ . The goal is to find a valid set of minimum size. Baswana et al. gave an $O(m \log{n})$ -time algorithm to compute a minimum-size valid set in $O(m \log{n})$ time, where $n = |V|$ and $m = |A|$ . Here we provide a simple $O(m)$ -time algorithm that uses the dominator tree $D$ of $G$ and a low-high order of it.

preprint2015arXiv

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

Let $G$ be a strongly connected directed graph. We consider the following three problems, where we wish to compute the smallest strongly connected spanning subgraph of $G$ that maintains respectively: the $2$ -edge-connected blocks of $G$ (\textsf{2EC-B}); the $2$ -edge-connected components of $G$ (\textsf{2EC-C}); both the $2$ -edge-connected blocks and the $2$ -edge-connected components of $G$ (\textsf{2EC-B-C}). All three problems are NP-hard, and thus we are interested in efficient approximation algorithms. For \textsf{2EC-C} we can obtain a $3/2$ -approximation by combining previously known results. For \textsf{2EC-B} and \textsf{2EC-B-C}, we present new $4$ -approximation algorithms that run in linear time. We also propose various heuristics to improve the size of the computed subgraphs in practice, and conduct a thorough experimental study to assess their merits in practical scenarios.

preprint2014arXiv

2-Edge Connectivity in Directed Graphs

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 paper 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. We show how to compute this relation in linear time so that we can report in constant time if two vertices are $2$ -edge-connected. We also show how 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.

preprint2013arXiv

Dominator Tree Certification and Independent Spanning Trees

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. But for some problems 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 independent 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.

preprint2013arXiv

Finding Dominators via Disjoint Set Union

The problem of finding dominators in a directed graph has many important applications, notably in global optimization of computer code. Although linear and near-linear-time algorithms exist, they use sophisticated data structures. We develop an algorithm for finding dominators that uses only a "static tree" disjoint set data structure in addition to simple lists and maps. The algorithm runs in near-linear or linear time, depending on the implementation of the disjoint set data structure. We give several versions of the algorithm, including one that computes loop nesting information (needed in many kinds of global code optimization) and that can be made self-certifying, so that the correctness of the computed dominators is very easy to verify.

preprint2010arXiv

Join-Reachability Problems in Directed Graphs

For a given collection G of directed graphs we define the join-reachability graph of G, denoted by J(G), as the directed graph that, for any pair of vertices a and b, contains a path from a to b if and only if such a path exists in all graphs of G. Our goal is to compute an efficient representation of J(G). In particular, we consider two versions of this problem. In the explicit version we wish to construct the smallest join-reachability graph for G. In the implicit version we wish to build an efficient data structure (in terms of space and query time) such that we can report fast the set of vertices that reach a query vertex in all graphs of G. This problem is related to the well-studied reachability problem and is motivated by emerging applications of graph-structured databases and graph algorithms. We consider the construction of join-reachability structures for two graphs and develop techniques that can be applied to both the explicit and the implicit problem. First we present optimal and near-optimal structures for paths and trees. Then, based on these results, we provide efficient structures for planar graphs and general directed graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Loukas Georgiadis

Research overview

Is this your work?

10 publications

Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems

An Experimental Study of Dynamic Dominators

Incremental $2$ -Edge-Connectivity in Directed Graphs

On Low-High Orders of Directed Graphs: Incremental Algorithms and Applications

A Note on Fault Tolerant Reachability for Directed Graphs

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

2-Edge Connectivity in Directed Graphs

Dominator Tree Certification and Independent Spanning Trees

Finding Dominators via Disjoint Set Union

Join-Reachability Problems in Directed Graphs

See the researcher in context

Building this map preview

Loukas Georgiadis

Research overview

Is this your work?

10 publications

Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems

An Experimental Study of Dynamic Dominators

Incremental 222-Edge-Connectivity in Directed Graphs

On Low-High Orders of Directed Graphs: Incremental Algorithms and Applications

A Note on Fault Tolerant Reachability for Directed Graphs

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

2-Edge Connectivity in Directed Graphs

Dominator Tree Certification and Independent Spanning Trees

Finding Dominators via Disjoint Set Union

Join-Reachability Problems in Directed Graphs

See the researcher in context

Building this map preview

Incremental $2$ -Edge-Connectivity in Directed Graphs