Polynomial universal traversing sequences for cycles are constructible

ABSTRACT

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 &Ogr;(d2n3logn) for n-vertex d-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 &Ogr; (n3) 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 &Ogr;(nlog n). Our universal traversing sequence has size &Ogr;(n4.76), and can be constructed in log-space.

REFERENCES

• 1: R. Aleliunas, A Simple Graph Traversing Problem MSe Thesis, University of Toronto (1978)
• 2: R. Aleliunas, R. M. Karp, R. J. Lipton,L. Lovasz, and C. Rackoff, Random Walks, Universal Traversing Sequences and The Complexity of Maze Problems Proc. ~Oth Annual Symposium on Foundations of Computer Science (1979) pp.218-223.
• 3: N. Alon , Y. Azar , Y. Ravid, Universal sequences for complete graphs, Discrete Applied Mathematics, v.27 n.1-2, p.25-28, May 1990 [doi>10.1016/0166-218X(90)90125-V]
• 4: A. Bar-Noy, A. Borodin, M. Karchmer, N. Linial, and M. Werman, Bo~mds on Universal Sequences TR C8-86-9, Hebrew Univer~ aitll, Jerusalem (1986) 16 pp.
• 5: A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. Tompa, Two Applications of Complementation via Inductive Counting manuscript (1987)
• 6: Michael F. Bridgland, Universal traversal sequences for paths and cycles, Journal of Algorithms, v.8 n.5, p.395-404, Sept. 1987 [doi>10.1016/0196-6774(87)90019-8]
• 7: D. Chiang,unpublished work (1985)
• 8: A. Cobham, Personal Communication, Irtcluded ill {121 (1986)
• 9: Stephen A. Cook , Pierre McKenzie, Problems complete for deterministic logarithmic space, Journal of Algorithms, v.8 n.5, p.385-394, Sept. 1987 [doi>10.1016/0196-6774(87)90018-6]
• 10: S. A. Cook and C. Rackoff, Space lower bounds by maze threadability on restricted machines,SIAM J. of Computing 9(1980), pp. 636-652.
• 11: N. Immerman, Nondeterministic Space is Closed Under Complement TR 552, Yale University (1987) 5 pp.
• 12: T. Ishizuka, Universal traversing sequences for cycles, B.A. Thesis, Wesleyan University, (1986) 22 pp.
• 13: S.A. Janowsky, unpublished work (1983)
• 14: H. Karloff, It. Paturi and J. Simon, Universal Sequences of Length n~(t~g") for Cliques, (1987) 2 pp. manuscript
• 15: H. It. Lewis and C. H. Papadimitriou, Symmetric Space Bounded Computation, Theoretical Computer Science 19 (1982), pp. 161- 187.
• 16: W.Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities J. of Computer and S{t~t~m Sciences 4 (1970) pp. 177-192.
• 17: M. Sipser, M.I.T. Lecture Notes on Complexity Theory M.I.T. (1985) 116 pp.
• 18: D. D. Utley, Construction of Universal Traversing Sequences for Cycles, B. A. Thesis, M. LT. (1985), 30 pp.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory