Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
type: Item
instance of: scholarly article
title: Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
zbMATH Open document ID: 0667.68078
DOI: 10.1016/0020-0190(88)90197-4
author: Howard Karloff
author: Ramamohan Paturi
author: Janos Simon
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: Explicit construction of universal traversal sequences of polynomial length for regular graphs is an open problem which was solved only for cycles. \textit{A. Bar-Noy}, \textit{A. Borodin}, \textit{M. Karchmer}, \textit{N. Liníal} and \textit{M. Werman} [SIAM J. Comput. 18, No.2, 268-277 (1989)] found universal sequences of length \(n^{\theta (n^ 2)}\) for cliques. The result is improved in this paper; the authors give a method to construct shorter universal traversal sequences for this class of regular graphs. These sequences have length \(n^{O(\log n)}\) and can be constructed uniformly in \(\log^ 2 n\) space.
reviewed by: C.Radu
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 4092793
zbMATH Keywords: space-bounded computation
zbMATH Keywords: explicit construction
zbMATH Keywords: universal traversal sequences
zbMATH Keywords: universal sequences
zbMATH Keywords: cliques
zbMATH Keywords: regular graphs
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90197-4
OpenAlex ID: W2070042895
cites work: Bounds on Universal Sequences
cites work: Universal traversal sequences for paths and cycles
cites work: Q5592246
description: scientific article; zbMATH DE number 4092793