3 papers
cs.DS2026
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…
cs.DS2025
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…
cs.DS2025
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…