License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.11
URN: urn:nbn:de:0030-drops-137836
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13783/
Calamai, Marco ;
Crescenzi, Pierluigi ;
Marino, Andrea
On Computing the Diameter of (Weighted) Link Streams
Abstract
A weighted link stream is a pair (V,?) comprising V, the set of nodes, and ?, the list of temporal edges (u,v,t,λ), where u,v are two nodes in V, t is the starting time of the temporal edge, and λ is its travel time. By making use of this model, different notions of diameter can be defined, which refer to the following distances: earliest arrival time, latest departure time, fastest time, and shortest time. After proving that any of these diameters cannot be computed in time sub-quadratic with respect to the number of temporal edges, we propose different algorithms (inspired by the approach used for computing the diameter of graphs) which allow us to compute, in practice very efficiently, the diameter of quite large real-world weighted link stream for several definitions of the diameter. Indeed, all the proposed algorithms require very often a very low number of single source (or target) best path computations. We verify the effectiveness of our approach by means of an extensive set of experiments on real-world link streams. We also experimentally prove that the temporal version of the well-known 2-sweep technique, for computing a lower bound on the diameter of a graph, is quite effective in the case of weighted link stream, by returning very often tight bounds.
BibTeX - Entry
@InProceedings{calamai_et_al:LIPIcs.SEA.2021.11,
author = {Calamai, Marco and Crescenzi, Pierluigi and Marino, Andrea},
title = {{On Computing the Diameter of (Weighted) Link Streams}},
booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)},
pages = {11:1--11:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-185-6},
ISSN = {1868-8969},
year = {2021},
volume = {190},
editor = {Coudert, David and Natale, Emanuele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13783},
URN = {urn:nbn:de:0030-drops-137836},
doi = {10.4230/LIPIcs.SEA.2021.11},
annote = {Keywords: Temporal graph, shortest path, diameter}
}
