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 <i>n</i> vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex <i>u</i> to vertex <i>v</i> is a path from <i>u</i> to <i>v</i> where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a (<i>u</i>, <i>v</i>)-journey for any pair of vertices <i>u</i>, <i>v</i>, <i>u</i> ≠ <i>v</i>. 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 <i>freely choose</i> availability instances for all edges and aims for temporal connectivity with very small <i>cost</i>; 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 <i>n</i>. 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 <i>given</i> 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 <i>P</i> = <i>N</i> <i>P</i>. 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 <i>minimal</i>, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least <i>n</i>log<i>n</i> 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: | 24 Jan 2024 13:16 |
| DOI: | 10.1007/s00224-017-9757-x |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3006091 |
Dimensions
Dimensions
