4 papers
An Efficient Algorithm for the Fast Delivery Problem
Iago A. Carvalho, Thomas Erlebach, Kleitos Papadopoulos
We study a problem where k autonomous mobile agents are initially located on distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous mobile agent has a prede…
An Interesting Structural Property Related to the Problem of Computing All the Best Swap Edges of a Tree Spanner in Unweighted Graphs
Davide Bilò, Kleitos Papadopoulos
In this draft we prove an interesting structural property related to the problem of computing {\em all the best swap edges} of a {\em tree spanner} in unweighted graphs. Previous p…
A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners
Davide Bilò, Kleitos Papadopoulos
Given a 2-edge connected, unweighted, and undirected graph with vertices and edges, a -tree spanner is a spanning tree of in which the ratio between the dist…
A fast algorithm for the gas station problem
Kleitos Papadopoulos, Demetres Christofides
In the gas station problem we want to find the cheapest path between two vertices of an -vertex graph. Our car has a specific fuel capacity and at each vertex we can fill our ca…