15 citations · 26 across the 17 of their papers we have counts for
24 papers · 1 filter
Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas +2
Computing edge-connected components in directed and undirected graphs is a fundamental and well-studied problem in graph algorithms. In a very recent breakthrough, Korhonen [STOC 2…
-Fault-Tolerant Strong Connectivity Oracles
Loukas Georgiadis, Evangelos Kosinas, Daniel Tsokaktsis
We study the problem of efficiently answering strong connectivity queries under two vertex failures. Given a directed graph with vertices, we provide a data structure with…
On 2-strong connectivity orientations of mixed graphs and related problems
Loukas Georgiadis, Dionysios Kefallinos, Evangelos Kosinas
A mixed graph is a graph that consists of both undirected and directed edges. An orientation of is formed by orienting all the undirected edges of , i.e., converting eac…
On maximal k-edge-connected subgraphs of undirected graphs
Loukas Georgiadis, Giuseppe F. Italiano, Evangelos Kosinas +1
We show how to find and efficiently maintain maximal k-edge-connected subgraphs in undirected graphs. In particular, we provide the following results. (1) A general framework for m…
Improved Linear-Time Algorithm for Computing the -Edge-Connected Components of a Graph
Loukas Georgiadis, Giuseppe F. Italiano, Evangelos Kosinas
We present an improved algorithm for computing the -edge-connected components of an undirected graph in linear time. The new algorithm uses only elementary data structures, and…
Computing the -Edge-Connected Components of a Graph in Linear Time
Loukas Georgiadis, Giuseppe F. Italiano, Evangelos Kosinas
We present the first linear-time algorithm that computes the -edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing…