论文标题
UCA型号的循环展开：距离标签
Loop unrolling of UCA models: distance labeling
论文作者
论文摘要
适当的循环弧（PCA）型号是一对$ m =（c，a）$，其中$ c $是一个圆圈，$ a $是$ c $的无包含弧家族，其极端是成对的。 Model $ m $代表一个digraph $ d $，每个$ v（a）$ a $ a \ in $ a \ in $ a \和一个边缘$ v（a）\ to v（b）$对于a（m）$中的每对arcs $ a，b \ a $ b $属于$ a $ a $ a $。对于$ k \ geq 0 $，$ k $ -th power $ d^k $ $ d $的顶点与$ d $和$ d $和$ v（a）\ to v（b）$是$ d^k $的边缘，当$ a \ neq b $，而$ v（a）$ v（a）$ n in $ d $ in $ d $ in $ k $的距离是$ d^k $。单位圆形ARC（UCA）模型是PCA模型$ u =（c，a）$，其中所有弧都具有相同的长度$ \ ell+1 $。如果$ \ ell $，则$ c $的长度$ c $，以及$ a $的极端是整数，那么$ u $是$（c，\ ell）$ - ca型号。对于$ i \ geq 0 $，通过用Arc $（S，S，S+I \ Ell+1）$替换每个Arc $（S，S+\ Ell+1）$获得型号$ i \ times u $的$ u $。如果$ u $代表digraph $ d $，则$ u $是$ k $ -multiplicative当$ i \ i \ times u $代表$ d^i $每$ 0 \ leq i \ leq k $。在本文中，我们设计了一种线性时间算法，以确定PCA型号$ M $等于$ K $ - 千年的UCA型号时，当$ k $作为输入时。该算法要么输出$ k $ - 千年的UCA型号$ u $相当于$ m $，要么是可以在线性时间进行身份验证的负证书。 我们的主要技术工具是那些相当于$ k $ - 多种UCA型号的PCA模型的新表征。对于$ k = 1 $，此特征为经典表示问题提供了一种新算法，该算法比以前已知的算法更简单。
A proper circular-arc (PCA) model is a pair $M = (C, A)$ where $C$ is a circle and $A$ is a family of inclusion-free arcs on $C$ whose extremes are pairwise different. The model $M$ represents a digraph $D$ that has one vertex $v(a)$ for each $a \in A$ and one edge $v(a) \to v(b)$ for each pair of arcs $a,b \in A(M)$ such that the beginning point of $b$ belongs to $a$. For $k \geq 0$, the $k$-th power $D^k$ of $D$ has the same vertices as $D$ and $v(a) \to v(b)$ is an edge of $D^k$ when $a\neq b$ and the distance from $v(a)$ to $v(b)$ in $D$ is at most $k$. A unit circular-arc (UCA) model is a PCA model $U = (C,A)$ in which all the arcs have the same length $\ell+1$. If $\ell$, the length $c$ of $C$, and the extremes of the arcs of $A$ are integer, then $U$ is a $(c,\ell)$-CA model. For $i \geq 0$, the model $i \times U$ of $U$ is obtained by replacing each arc $(s,s+\ell+1)$ with the arc $(s,s+i\ell+1)$. If $U$ represents a digraph $D$, then $U$ is $k$-multiplicative when $i \times U$ represents $D^i$ for every $0 \leq i \leq k$. In this article we design a linear time algorithm to decide if a PCA model $M$ is equivalent to a $k$-multiplicative UCA model when $k$ is given as input. The algorithm either outputs a $k$-multiplicative UCA model $U$ equivalent to $M$ or a negative certificate that can be authenticated in linear time. Our main technical tool is a new characterization of those PCA models that are equivalent to $k$-multiplicative UCA models. For $k=1$, this characterization yields a new algorithm for the classical representation problem that is simpler than the previously known algorithms.
