Universal Traversal Sequences

DOI10.2307/2975606MaRDI QIDQ4293904zbMATH OpenOpenAlexFDO

Authors Joan Feigenbaum, Nick Reingold

Publication date 10 July 1994

Published in The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2975606

zbMATH Keywords

complexity theorylogspace computationuniversal traversal sequences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Universal traversal sequences for paths and cycles
• Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
• scientific article; zbMATH DE number 1796948
• Universal traversal sequences with backtracking.

Cited in

(6)

• On a universal chain problem
• Universal sequences
• Universal traversal sequences for expander graphs
• scientific article; zbMATH DE number 3911721 (Why is no real title available?)
• Universal traversal sequences for paths and cycles
• Finite paths are universal

This page was built for publication: Universal Traversal Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4293904)