Dr Eleni Akrida eleni.akrida@durham.ac.uk
Associate Professor
Dr Eleni Akrida eleni.akrida@durham.ac.uk
Associate Professor
L. Gasieniec
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
P.G. 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, and at most the optimal cost plus 2. To show this, we prove a lower bound on the cost for any undirected graph. 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=NP. On the positive side, we show that in dense graphs with random edge availabilities, all but Θ(n) labels are redundant whp. 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.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 13th Workshop on Approximation and Online Algorithms (WAOA) |
Start Date | Sep 17, 2015 |
End Date | Sep 18, 2015 |
Acceptance Date | Jul 24, 2015 |
Online Publication Date | Jan 13, 2016 |
Publication Date | Jan 13, 2016 |
Deposit Date | Sep 30, 2015 |
Publicly Available Date | Jan 13, 2017 |
Publisher | Springer Verlag |
Pages | 84-96 |
Series Title | Lecture notes in computer science |
Series Number | 9499 |
Book Title | Approximation and online algorithms : 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised selected papers. |
ISBN | 9783319286839 |
DOI | https://doi.org/10.1007/978-3-319-28684-6_8 |
Public URL | https://durham-repository.worktribe.com/output/1151994 |
Accepted Conference Proceeding
(244 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007%2F978-3-319-28684-6_8
Narrowing and Stretching: Addressing the Challenge of Multi-track Programming
(2022)
Presentation / Conference Contribution
Temporal Flows in Temporal Networks
(2017)
Presentation / Conference Contribution
On Verifying and Maintaining Connectivity of Interval Temporal Networks
(2015)
Presentation / Conference Contribution
How fast can we reach a target vertex in stochastic temporal graphs?
(2019)
Presentation / Conference Contribution
Temporal vertex cover with a sliding time window
(2018)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search