Polynomial universal traversing sequences for cycles are constructible
Polynomial universal traversing sequences for cycles are constructible
复制标题
循环的多项式通用运行序列是可构造的
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
S. Istrail
中科院分区：
文献类型：
--
作者：
S. Istrail
本文构造了第一个多项式泛圈遍历序列，解决了S。Cook和R.阿莱柳纳斯河卡普河利普顿湖洛瓦斯角Rackoff（1979）[2]在2-正则图的情况下。在[2]中，用概率论的方法证明<italic>了n</italic>-顶点<italic>d</italic>-正则图的（<supscrpt>d2</supscrpt><supscrpt>n3</supscrpt><italic>logn</italic>）<italic></italic><italic></italic>对于循环，Janowsky（1983）[13]和Cobham（1986）[8]将非构造性上界改进为（<italic>n</italic><supscrpt>3</supscrpt>）。以前，最好的明确的构造圈是由于Bridgland（1986）和A. Bar-Noy，A. Borodin，M. Karchmer，N. Linial和M. Werman（1986），并有size（<italic>n<supscrpt>log n</supscrpt></italic>）。
我们的通用遍历序列的大小为（<italic>n</italic><supscrpt>4.76</supscrpt>），并且可以在对数空间中构造。
The paper constructs the first polynomial universal traversing sequences for cycles, solving an open problem of S. Cook and R. Aleliunas, R. Karp, R. Lipton, L. Lovasz, C. Rackoff (1979) [2] in the case of 2-regular graphs. The existence of universal traversing sequences of size <italic>&Ogr;</italic>(<italic>d</italic><supscrpt>2</supscrpt><italic>n</italic><supscrpt>3</supscrpt><italic>logn</italic>) for <italic>n</italic>-vertex <italic>d</italic>-regular graphs was established in [2] by a probabilistic argument, which was inherently non-constructive. For the cycles, the non-constructive upper bound was improved to <italic>&Ogr;</italic> (<italic>n</italic><supscrpt>3</supscrpt>) by Janowsky (1983) [13] and Cobham (1986) [8]. Previously, the best explicit constructions for cycles were due to Bridgland (1986) and A. Bar-Noy, A. Borodin, M. Karchmer, N. Linial, and M. Werman (1986), and have size <italic>&Ogr;</italic>(<italic>n<supscrpt>log n</supscrpt></italic>).
Our universal traversing sequence has size <italic>&Ogr;</italic>(<italic>n</italic><supscrpt>4.76</supscrpt>), and can be constructed in log-space.