Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs

DOI10.1137/0221067zbMath0760.68038OpenAlexW2018763818MaRDI QIDQ4027857

Martin Tompa

Publication date: 9 March 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0221067

zbMATH Keywords

cycleslower boundgraph traversaluniversal traversal sequencescircumnavigationreflecting sequences

Mathematics Subject Classification ID

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

Related Items (4)

Universal traversal sequences with backtracking. ⋮ Length lower bounds for reflecting sequences and universal traversal sequences ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space ⋮ Lower bounds on the length of universal traversal sequences

This page was built for publication: Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs