Exploration of Always $S$-Connected Temporal Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912920291508224 |
|---|---|
| author | Adamson, Duncan Spirakis, Paul G |
| author_facet | Adamson, Duncan Spirakis, Paul G |
| contents | \emph{Temporal graphs} are a generalisation of (static) graphs, defined by a sequence of \emph{snapshots}, each a static graph defined over a common set of vertices. \emph{Exploration} problems are one of the most fundamental and most heavily studied problems on temporal graphs, asking if a set of $m$ agents can visit every vertex in the graph, with each agent only allowed to traverse a single edge per snapshot. In this paper, we introduce and study \emph{always $S$-connected} temporal graphs, a generalisation of always connected temporal graphs where, rather than forming a single connected component in each snapshot, we have at most $\vert S \vert$ components, each defined by the connection to a single vertex in the set $S$. We use this formulation as a tool for exploring graphs admitting an \emph{$(r,b)$-division}, a partitioning of the vertex set into disconnected components, each of which is $S$-connected, where $\vert S \vert \leq b$.
We show that an always $S$-connected temporal graph with $m = \vert S \vert$ and an average degree of $Δ$ can be explored by $m$ agents in $O(n^{1.5} m^3 Δ^{1.5}\log^{1.5}(n))$ snapshots. Using this as a subroutine, we show that any always-connected temporal graph with treewidth at most $k$ can be explored by a single agent in $O\left(n^{4/3} k^{5.5}\log^{2.5}(n)\right)$ snapshots, improving on the current state-of-the-art for small values of $k$. Further, we show that interval graph with only a small number of large cliques can be explored by a single agent in $O\left(n^{4/3} \log^{2.5}(n)\right)$ snapshots. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_19657 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exploration of Always $S$-Connected Temporal Graphs Adamson, Duncan Spirakis, Paul G Data Structures and Algorithms \emph{Temporal graphs} are a generalisation of (static) graphs, defined by a sequence of \emph{snapshots}, each a static graph defined over a common set of vertices. \emph{Exploration} problems are one of the most fundamental and most heavily studied problems on temporal graphs, asking if a set of $m$ agents can visit every vertex in the graph, with each agent only allowed to traverse a single edge per snapshot. In this paper, we introduce and study \emph{always $S$-connected} temporal graphs, a generalisation of always connected temporal graphs where, rather than forming a single connected component in each snapshot, we have at most $\vert S \vert$ components, each defined by the connection to a single vertex in the set $S$. We use this formulation as a tool for exploring graphs admitting an \emph{$(r,b)$-division}, a partitioning of the vertex set into disconnected components, each of which is $S$-connected, where $\vert S \vert \leq b$. We show that an always $S$-connected temporal graph with $m = \vert S \vert$ and an average degree of $Δ$ can be explored by $m$ agents in $O(n^{1.5} m^3 Δ^{1.5}\log^{1.5}(n))$ snapshots. Using this as a subroutine, we show that any always-connected temporal graph with treewidth at most $k$ can be explored by a single agent in $O\left(n^{4/3} k^{5.5}\log^{2.5}(n)\right)$ snapshots, improving on the current state-of-the-art for small values of $k$. Further, we show that interval graph with only a small number of large cliques can be explored by a single agent in $O\left(n^{4/3} \log^{2.5}(n)\right)$ snapshots. |
| title | Exploration of Always $S$-Connected Temporal Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.19657 |