Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata

• 1 November 1996
• journal article
• Published by Elsevier in Information and Computation
• Vol. 130  (2) , 101-129
• https://doi.org/10.1006/inco.1996.0085

Abstract

Keywords

• UNDIRECTED GRAPH TRAVERSAL
• TIME-SPACE TRADEOFFS
• GRAPH AUTOMATON
• LINEAR TIME
• LOWER BOUND
• LINEAR SPACE
• TURING MACHINE
• COMPLEXITY CLASS
• POLYNOMIAL FACTORIZATION
• DEPTH FIRST SEARCH
• RANDOM WALK