{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib2j2rgcavaraofj67qrn3yddpbykcxjcz3e5v7azwrls7o6ucg2q",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mepo4nioxu32"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.12126v1",
  "publishedAt": "2026-02-13T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Daniele Carnevale",
    "Gianlorenzo D'Angelo"
  ],
  "textContent": "**Authors:** Daniele Carnevale, Gianlorenzo D'Angelo\n\nTemporal graphs represent networks in which connections change over time, with edges available only at specific moments. Motivated by applications in logistics, multi-agent information spreading, and wireless networks, we introduce the D-Temporal Multi-Broadcast (D-TMB) problem, which asks for scheduling the availability of edges so that a predetermined subset of sources reach all other vertices while optimizing the worst-case temporal distance D from any source. We show that D-TMB generalizes ReachFast (arXiv:2112.08797). We then characterize the computational complexity and approximability of D-TMB under six definitions of temporal distance D, namely Earliest-Arrival (EA), Latest-Departure (LD), Fastest-Time (FT), Shortest-Traveling (ST), Minimum-Hop (MH), and Minimum-Waiting (MW). For a single source, we show that D-TMB can be solved in polynomial time for EA and LD, while for the other temporal distances it is NP-hard and hard to approximate within a factor that depends on the adopted distance function. We give approximation algorithms for FT and MW. For multiple sources, if feasibility is not assumed a priori, the problem is inapproximable within any factor unless P = NP, even with just two sources. We complement this negative result by identifying structural conditions that guarantee tractability for EA and LD for any number of sources.",
  "title": "Optimizing Distances for Multi-Broadcast in Temporal Graphs"
}