标题： 时间探索随机生成树模型 显示英文标题

标题： Temporal Exploration of Random Spanning Tree Models

摘要： 时间图探索问题（TEXP）以一个时间图作为输入，即同一顶点集上的图序列$(G_i)_{i\in \mathbb{N}}$，并要求一条最短长度的行走，该行走访问所有顶点，其中$i$-第步使用来自$G_i$的边。 如果每个这样的$G_i$都是连通的，那么存在长度为$n^2$的探索，并且已知这是常数因子下的最佳可能。 对于受限的时间图类，已经获得了更精细的下界和上界，然而，对于几个基本类，已知界限之间仍然存在很大差距，并且尚不清楚时间图的哪些属性使其难以探索。 鉴于对此问题理解有限以及时间图探索问题在时间图理论中的核心作用，我们在随机设置中研究该问题。 我们引入了随机生成树（RST）模型，该模型由一组$n$顶点的树以及该集合上的任意概率分布$\mu$组成。 由RST模型生成的随机时间图是从$\mu$中独立采样的序列。我们开始对这种随机时间图中的时序图探索问题进行系统研究，并建立了探索时间的紧密一般性界限。我们的第一个主要结果证明，任何RST模型都可以以高概率（w.h.p.）在$O(n^{3/2})$时间内被探索，并且我们证明这个界限在常数因子范围内是紧的。这展示了对抗设置和随机设置之间的根本差异。我们的第二个主要结果表明，如果RST的所有树都是具有$m$条边的固定图的子图，那么它可以在$O(m)$时间内被探索。 显示英文摘要

摘要： The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs $(G_i)_{i\in \mathbb{N}}$ on the same vertex set, and asks for a walk of shortest length visiting all vertices, where the $i$-th step uses an edge from $G_i$. If each such $G_i$ is connected, then an exploration of length $n^2$ exists, and this is known to be the best possible up to a constant. More fine-grained lower and upper bounds have been obtained for restricted temporal graph classes, however, for several fundamental classes, a large gap persists between known bounds, and it remains unclear which properties of a temporal graph make it inherently difficult to explore. Motivated by this limited understanding and the central role of the Temporal Graph Exploration problem in temporal graph theory, we study the problem in a randomised setting. We introduce the Random Spanning Tree (RST) model, which consists of a set of $n$-vertex trees together with an arbitrary probability distribution $\mu$ over this set. A random temporal graph generated by the RST model is a sequence of independent samples drawn from $\mu$. We initiate a systematic study of the Temporal Graph Exploration problem in such random temporal graphs and establish tight general bounds on exploration time. Our first main result proves that any RST model can, with high probability (w.h.p.), be explored in $O(n^{3/2})$ time, and we show that this bound is tight up to a constant factor. This demonstrates a fundamental difference between the adversarial and random settings. Our second main result shows that if all trees of an RST are subgraphs of a fixed graph with $m$ edges then, w.h.p.\ , it can be explored in $O(m)$ time.