Exploration of $k$-edge-deficient temporal graphs in linear time
We study the Temporal Exploration problem, where an agent must visit all vertices of a temporal graph while traversing at most one available edge per time step. Unlike static graphs, which can be explored in linear time, temporal constraints can substantially increase exploration time even when every snapshot of the graph is connected. To better understand the source of this complexity, we focus on a near-static setting and consider always-connected $k$-edge-deficient temporal graphs, in which each snapshot is connected and differs from a fixed underlying $n$-vertex graph by at most $k$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.15833
curl -X POST /api/v1/records/arxiv/2605.15833/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.15833/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'