A. Borodin
ABSTRACT
Universal traversal sequences for d-regular n-vertex graphs require length Ω(d2n2 + dn2 log n/d), for 3 ≤ d ≤ n/3 - 2. This is nearly tight for d = Θ(n). We also introduce and study several variations on the problem, e.g. edge-universal traversal sequences, showing how improved lower bounds on these would improve the bounds given above.
- 1.R. Aleliunas. A Simple Graph Traversing Problem. Master's thesis, University of Toronto, April 1978. TechnicM Report No. 120.Google Scholar
- 2.R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lov~sz, and C. R~ckoff. Random walks, universal traversal sequences, and the complexity of m~ze problems. In 20th Annual Symposium on Foundations of Computer Science, pages 218-223, San Juan, Puerto Rico, October 1979.Google ScholarDigital Library
- 3.N. Alon and Y. Ravid. Universal sequences for complete graphs. Discrete Applied Mathematics. To appear. Google ScholarDigital Library
- 4.B. Awerbttch, O. Goldreich, D. Peleg, and R. Vainish. A Tradeoff Between Information and Communication in Broadcast Protocols. Technical Memorandum MIT/LCS/TM-365, MIT, July 1988.Google Scholar
- 5.A. Bar-Noy, A. Borodin, M. Karchmer, N. Linial, and M. Werman. Bounds on Universal Sequences. Technical Report CS-86-9, The Hebrew University of Jerusalem, June 1986. To appear in SIAM Journal on Computing. Google ScholarDigital Library
- 6.P. Beame, A. Borodin, P. Raghavan, W. L. Ruzzo, and M. Tompa. Time-space tradeoffs for undirected graph connectivity. In preparation.Google Scholar
- 7.A. Borodin, S. A. Cook, P. W. Dymond, W. L. l~uzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3), June 1989. To appear. Preliminary version appeared in the Third Annual Conference on Structure in Complezitgt Theory, pages 116- 126, June 1988. Google ScholarDigital Library
- 8.A. Borodin, W. L. P~uzzo, and M. Tompa. Lower Bounds on the Length of Universal Traversal Sequences. Technical Report 89-03- 02, University of Washington, March 1989.Google ScholarDigital Library
- 9.M. F. Bridgland. Universal traversal sequences for paths and cycles. J. of Algorithms, 8(3):395-404, 1987. Google ScholarDigital Library
- 10.A. Broder, A. Karlin, P. Raghavan, and E. Upfal. Trading space for time in undirected s-t connectivity. In Proceedings of the Twenty- First Annual A CM Sympo8ium on Theory of Computing, Seattle, WA, May 1989. Google ScholarDigital Library
- 11.A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari. The electrical resistance of a graph captures its commute and cover times. In Proceedings of the Twenty- First Annual A UM Symposium on Theory of Computing, Seattle, WA, May 1989. Google ScholarDigital Library
- 12.S. A. Cook and C. W. Rackoff. Space lower bounds for maze threadability on restricted machines. SIAM Journal on Computing, 9(3):636-652, August 1980.Google ScholarDigital Library
- 13.I. N. Herstein. Topics in Algebra. John Wiley & Sons, New York, second edition, 1975.Google Scholar
- 14.S. Istrail. Polynomial universal traversing sequences for cycles are constructible. In Proceedings of the Twentieth Annual A CM Symposium on Theory of Computing, pages 491- 503, Chicago, Illinois, May 1988. Google ScholarDigital Library
- 15.J. Kahn, N. Linial, N. Nisan, and M. Saks. On the cover time of random walks in graphs. Journal of Theoretical Probability, 1989. To appear.Google ScholarCross Ref
- 16.tt. J. Karloff, R. Paturi, and J. Simon. Universal traversal sequences of length nO(l~gn) for cliques. Information Processing Letters, 28:241-243, August 1988. Google ScholarDigital Library
- 17.L. Lovfisz. Combinatorial Problems and Ezercises. North-Holland Publishing Company, Amsterdam, 1979.Google Scholar
Index Terms
- Lower bounds on the length of universal traversal sequences
Recommendations
Length lower bounds for reflecting sequences and universal traversal sequences
A universal traversal sequence for the family of all connected d -regular graphs of order n with an edge-labeling is a sequence of { 0 , 1 , , d - 1 } that traverses every graph of the family starting at every vertex of the graph. Reflecting sequences ...
Lower Bounds on Universal Traversal Sequences Based on Chains of Length Five
Universal traversal sequences for cycles require length (n1.43), improving the previous bound of (n1.33). For d 3, universal traversal sequences for d-regular graphs require length (d0.57n2.43). For constant d, the best previous bound was (n2.33).
Lower bounds for optimal alignments of binary sequences
In parametric sequence alignment, optimal alignments of two sequences are computed as a function of matches, mismatches and spaces, producing many different optimal alignments. In the two-parameter case, Gusfield et al shows that the number of distinct ...
Comments