George B. Mertzios

George B. Mertzios

Auto-generated profile, based on publicly available information

George B. Mertzios

Durham University

Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
5 July 2018 in Algorithmica
Verified
Journal Article
Open access
PDF file
GMGeorge B. Mertzios
George B. Mertzios
OMOthon Michail
Othon Michail
PSPaul Spirakis
Paul Spirakis
In this work we consider temporal networks, i.e. networks defined by a labeling \(\lambda \) assigning to each edge of an underlying graph G a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular, we consider time-respecting paths, i.e. paths whose edges are assigned by \(\lambda \) a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally, we propose two cost minimization parameters for temporal network design. One is the temporality of G, in which the goal is to minimize the maximum number of labels of an edge, and the other is the temporal cost of G, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some connectivity constraint. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.

1 August 2021 in Journal of Computer and System Sciences
Verified
Journal Article
Closed access
JEJessica Enright
Jessica Enright
KMKitty Meeks
Kitty Meeks
GMGeorge B. Mertzios
George B. Mertzios
VZViktor Zamaraev
Viktor Zamaraev


3 April 2017 in Theory of Computing Systems
Verified
Journal Article
Open access
PDF file
EAEleni C. Akrida
Eleni C. Akrida
LGLeszek Gąsieniec
Leszek Gąsieniec
GMGeorge B. Mertzios
George B. Mertzios
PSPaul Spirakis
Paul Spirakis
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (u, v)-journey for any pair of vertices u, v, u ≠ v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P = N P. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlogn labels.

28 November 2012 in Algorithmica
Verified
Journal Article
Closed access
PDF file
JDJosep Díaz
Josep Díaz
LGLeslie Ann Goldberg
Leslie Ann Goldberg
GMGeorge B. Mertzios
George B. Mertzios
DRDavid Richerby
David Richerby
MSMaria Serna
Maria Serna
PSPaul G. Spirakis
Paul G. Spirakis

1 January 2014
Verified
Book Chapter
Closed access
PDF file
GMGeorge B. Mertzios
George B. Mertzios
SNSotiris Nikoletseas
Sotiris Nikoletseas
CRChristoforos L. Raptopoulos
Christoforos L. Raptopoulos
PSPaul Spirakis
Paul Spirakis