Time-space tradeoffs for undirected graph traversal
Authors:
- P. BeamePBP. Beame
- A. BorodinABA. Borodin
- P. RaghavanPRP. Raghavan
- W.L. RuzzoWRW.L. Ruzzo
- M. TompaMTM. Tompa
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 429-438
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- Two Applications of Inductive Counting for Complementation ProblemsSIAM Journal on Computing, 1989
- Lower bounds on the length of universal traversal sequences1989
- Trading space for time in undirected s-t connectivity1989
- Universal traversal sequences of length nO(log n) for cliquesInformation Processing Letters, 1988
- Polynomial universal traversing sequences for cycles are constructible1988
- Universal traversal sequences for paths and cyclesJournal of Algorithms, 1987
- Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space ImplementationsSIAM Journal on Computing, 1982
- Space Lower Bounds for Maze Threadability on Restricted MachinesSIAM Journal on Computing, 1980
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935