3 papers
cs.DM2026
Structural Lemmas on Temporal Connectivity
Daniele Carnevale, Arnaud Casteigts, David Schindl
This paper presents several lemmas on the structure of temporal connectivity in temporal graphs. Some of these lemmas are adapted from the literature on gossip from the 70-90's and…
cs.DS2026
Minimum Temporal Spanners in Happy Graphs
Arnaud Casteigts, Hendrik Molter, Meirav Zehavi
Temporal graphs have edge sets that change over discrete time steps. Such graphs are temporally connected (TC) if all pairs of vertices can reach each other using paths that traver…
cs.CC2026
On the Hardness of Finding Temporally Connected Subgraphs of Any Size
Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz
Temporal graphs are graphs whose edges are present only at certain points in time. Reachability in these graphs is defined via temporal paths, in which edges are traversed in chron…