Exploration of k-Edge-Deficient Temporal Graphs

Erlebach, Thomas; Spooner, Jakob T.

Abstract

A temporal graph with lifetime L is a sequence of L graphs G1, . . . , GL, called layers, all of which have the same vertex set V but can have different edge sets. The underlying graph is the graph with vertex set V that contains all the edges that appear in at least one layer. The temporal graph is always-connected if each layer is a connected graph, and it is k-edge-decient if each layer contains all except at most k edges of the underlying graph. For a given start vertex s, a temporal exploration is a temporal walk that starts at s, traverses at most one edge in each layer, and visits all vertices of the temporal graph. We show that always- connected, k-edge-decient temporal graphs with sucient lifetime can always be explored in O(kn log n) time steps. We also construct always-connected, k-edge- decient temporal graphs for which any exploration requires (n log k) time steps. For always-connected, 1-edge-decient temporal graphs, we show that O(n) time steps suce for temporal exploration.

Citation

Erlebach, T., & Spooner, J. T. (2022). Exploration of k-Edge-Deficient Temporal Graphs. Acta Informatica, 59(4), 387-407. https://doi.org/10.1007/s00236-022-00421-5

• Journal Article Type: Article
• Acceptance Date: Mar 28, 2022
• Online Publication Date: Aug 27, 2022
• Publication Date: 2022-08
• Deposit Date: Apr 10, 2022
• Publicly Available Date: Aug 30, 2022
• Journal: Acta Informatica
• Print ISSN: 0001-5903
• Electronic ISSN: 1432-0525
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 59
• Issue: 4
• Pages: 387-407
• DOI: https://doi.org/10.1007/s00236-022-00421-5
• Public URL: https://durham-repository.worktribe.com/output/1210332