Exploration of k k -edge-deficient temporal graphs in linear time

Ivan Lahtin, Viktor Zamaraev · 2026

Read Exploration of k k -edge-deficient temporal graphs in linear time by Ivan Lahtin, Viktor Zamaraev (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15833.txt.

Description

Ivan Lahtin and Viktor Zamaraev settle whether near-static temporal graphs allow linear-time exploration. They study always-connected k-edge-deficient temporal graphs, each snapshot connected and at most k edges from a fixed base graph. Prior work gave an O(kn log n) schedule and an Omega(n log k) lower bound, They prove any such graph admits an O(nk log k) schedule, computable in polynomial time. For constant k this gives order-optimal Theta(n) time, so temporal exploration here keeps static traversal's linear character.

Catalog record

CREATORIvan Lahtin, Viktor Zamaraev
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45833
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.15833

Browse the full library · About the Tower of Babel