Dr Eleni Akrida eleni.akrida@durham.ac.uk
Associate Professor
On temporally connected graphs of small cost
Akrida, E.C.; Gasieniec, L.; Mertzios, G.B.; Spirakis, P.G.
Authors
L. Gasieniec
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
P.G. Spirakis
Abstract
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.
Citation
Akrida, E., Gasieniec, L., Mertzios, G., & Spirakis, P. (2016). On temporally connected graphs of small cost. In Approximation and online algorithms : 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised selected papers (84-96). https://doi.org/10.1007/978-3-319-28684-6_8
Conference Name | 13th Workshop on Approximation and Online Algorithms (WAOA) |
---|---|
Conference Location | Patras, Greece |
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 | Mar 28, 2024 |
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 |
Files
Accepted Conference Proceeding
(0)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007%2F978-3-319-28684-6_8
You might also like
Narrowing and Stretching: Addressing the Challenge of Multi-track Programming
(2022)
Conference Proceeding
Connected Subgraph Defense Games
(2021)
Journal Article
The temporal explorer who returns to the base
(2021)
Journal Article
How fast can we reach a target vertex in stochastic temporal graphs?
(2020)
Journal Article
Connected Subgraph Defense Games
(2019)
Book Chapter
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
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