{"id":"arxiv/2605.15833","url":"https://arxiv.org/abs/2605.15833","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Exploration of $k$-edge-deficient temporal graphs in linear time","domain":"cs.DS","source":"arxiv","authors":["Ivan Lahtin","Viktor Zamaraev"],"reviews":0,"subject":"cs.DS","summary":"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$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-15","reactions":{}}