Akrida, Eleni C 
ORCID: 0000-0002-1126-1623, Gasieniec, Leszek ORCID: 0000-0003-1809-9814, Mertzios, George B and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2017)
The Complexity of Optimal Design of Temporally Connected Graphs.
THEORY OF COMPUTING SYSTEMS, 61 (3).
pp. 907-944.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
paper.pdf - Author Accepted Manuscript Download (818kB) |
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/application_atom+xml.png) |
Atom XML (admin)
2017-05-12T11:29:44Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T12:26:06Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T13:25:19Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T14:25:23Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T15:25:30Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T16:26:00Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T17:25:22Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T18:26:12Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T19:25:40Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T20:26:00Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T21:26:22Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T22:27:06Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-12T23:32:49Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T01:27:43Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T02:27:03Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T03:27:07Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T04:49:53Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T05:26:59Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T06:26:10Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T07:26:29Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T08:26:54Z.atom - Unspecified Download (0B) |
|
Atom XML (admin)
2017-05-13T09:26:12Z.atom - Unspecified Download (0B) |
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. 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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Temporal graphs, Network design, Temporally connected, Minimal graph, APX-hard, Random input |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 28 Feb 2017 09:36 |
| Last Modified: | 19 Jan 2023 07:15 |
| DOI: | 10.1007/s00224-017-9757-x |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3006091 |
Dimensions
Dimensions
