Kleitos Papadopoulos

dblp:202/2516 · DBLP profile ↗
← Back
4ranked-venue papers
1as first author
1since 2021 · last 2021
0000-0002-7086-0335ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 4 · 1 first-author · 1 since 2021Databases, data management, data science and information retrieval · 1 · 1 first-author
YearPublicationVenuePosition
2021 On the fast delivery problem with one or two packages
Iago A. Carvalho, Thomas Erlebach, Kleitos Papadopoulos
J. Comput. Syst. Sci.3
2019 An Efficient Algorithm for the Fast Delivery Problem
Iago A. Carvalho, Thomas Erlebach, Kleitos Papadopoulos
FCT3
2018 A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
abstract
Given a 2-edge connected, unweighted, and undirected graph G with n vertices and m edges, a sigma-tree spanner is a spanning tree T of G in which the ratio between the distance in T of any pair of vertices and the corresponding distance in G is upper bounded by sigma. The minimum value of sigma for which T is a sigma-tree spanner of G is also called the stretch factor of T. We address the fault-tolerant scenario in which each edge e of a given tree spanner may temporarily fail and has to be replaced by a best swap edge, i.e. an edge that reconnects T-e at a minimum stretch factor. More precisely, we design an O(n^2) time and space algorithm that computes a best swap edge of every tree edge. Previously, an O(n^2 log^4 n) time and O(n^2+m log^2n) space algorithm was known for edge-weighted graphs [Bilò et al., ISAAC 2017]. Even if our improvements on both the time and space complexities are of a polylogarithmic factor, we stress the fact that the design of a o(n^2) time and space algorithm would be considered a breakthrough.
Davide Bilò, Kleitos Papadopoulos
ISAAC2
2018 A fast algorithm for the gas station problem
Kleitos Papadopoulos, Demetres Christofides
Inf. Process. Lett.1