论文标题
半随机树过程
The semi-random tree process
论文作者
论文摘要
在线半随机图过程是一个单人游戏，从$ n $顶点上的空图开始。在每一轮比赛中，一个播放器（称为建造者）都会在随机和以前的回合中独立于随机选择的顶点$ v $呈现，并构建了他们选择的边缘，而这些边缘是事件到$ v $。受半随机图流程的最新进展的启发，我们定义了一个广义的在线半随机模型。 我们分析了一个特定实例，该实例与原始的半随机图过程共享相似的功能，并确定经典图形属性的打击时间，最低度$ k $，$ k $ - 连接性，完美匹配的遏制，汉密尔顿周期和$ h $ flator的固定图$ h $具有额外的树状属性。在此过程中，我们引起了可能具有独立关注的著名奥尔德·布罗德算法的一些后果。
The online semi-random graph process is a one-player game which starts with the empty graph on $n$ vertices. At every round, a player (called Builder) is presented with a vertex $v$ chosen uniformly at random and independently from previous rounds, and constructs an edge of their choice that is incident to $v$. Inspired by recent advances on the semi-random graph process, we define a family of generalised online semi-random models. We analyse a particular instance that shares similar features with the original semi-random graph process and determine the hitting times of the classical graph properties minimum degree $k$, $k$-connectivity, containment of a perfect matching, a Hamiltonian cycle and an $H$-factor for a fixed graph $H$ possessing an additional tree-like property. Along the way, we derive a few consequences of the famous Aldous-Broder algorithm that may be of independent interest.
