3 citations · 3 across the 7 of their papers we have counts for
13 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…
Efficient Contractions of Dynamic Graphs -- with Applications
Monika Henzinger, Evangelos Kosinas, Robin Münk +1
A non-trivial minimum cut (NMC) sparsifier is a multigraph that preserves all non-trivial minimum cuts of a given undirected graph . We introduce a flexible data struc…
An Optimal -Fault-Tolerant Connectivity Oracle
Evangelos Kosinas
We present an optimal oracle for answering connectivity queries in undirected graphs in the presence of at most three vertex failures. Specifically, we show that we can process a g…
Online Drone Scheduling for Last-mile Delivery
Saswata Jana, Giuseppe F. Italiano, Manas Jyoti Kashyop +3
Delivering a parcel from the distribution hub to the customer's doorstep is called the \textit{last-mile delivery} step in delivery logistics. In this paper, we study a hybrid {\it…
-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…
Connectivity Oracles for Predictable Vertex Failures
Bingbing Hu, Evangelos Kosinas, Adam Polak
The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous…
Computing the -Edge-Connected Components in Linear Time
Evangelos Kosinas
We provide a deterministic algorithm for computing the -edge-connected components of an undirected multigraph in linear time. There were probably good indications that this comp…
Connectivity Queries under Vertex Failures: Not Optimal, but Practical
Evangelos Kosinas
We revisit once more the problem of designing an oracle for answering connectivity queries in undirected graphs in the presence of vertex failures. Specifically, given an undirecte…
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…
Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems
Loukas Georgiadis, Evangelos Kosinas
A directed graph is twinless strongly connected if it contains a strongly connected spanning subgraph without any pair of antiparallel (or twin) edges. The twinless stron…