5 papers
Hiding a Vertex from the Temporal Explorer: A Lower Bound for Degree-Bounded Temporal Graphs
Daniele Carnevale
A temporal graph is a sequence of graphs on a common set of vertices, its snapshots, one for each time step. An agent, knowing the entire sequence in advance, may at each time…
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…
Optimizing Distances for Multi-Broadcast in Temporal Graphs
Daniele Carnevale, Gianlorenzo D'Angelo
Temporal graphs represent networks in which connections change over time, with edges available only at specific moments. Motivated by applications in logistics, multi-agent informa…
Approximating Optimal Labelings for Temporal Connectivity
Daniele Carnevale, Gianlorenzo D'Angelo, Martin Olsen
In a temporal graph the edge set dynamically changes over time according to a set of time-labels associated with each edge that indicates at which time-steps the edge is available.…
Dismountability in Temporal Cliques Revisited
Daniele Carnevale, Arnaud Casteigts, Timothée Corsini
A temporal graph is a graph whose edges are available only at certain points in time. It is temporally connected if the nodes can reach each other by paths that traverse the edges…