RUSPACE(log n ) $\subseteq$ DSPACE(log 2 n /log log n )

descriptionPublicationkeyboard_double_arrow_right Article 01 Sep 1998Publisher:Springer Science and Business Media LLCJournal:Theory of Computing Systems, volume 31, pages 539-550 (issn: 1432-4350, eissn: 1433-0490,

Copyright policy )Funded by:NSF | Computational Complexity ...

Authors: Eric Allender; Klaus-Jörn Lange;

doi: 10.1007/s002240000102

RUSPACE(log n ) $\subseteq$ DSPACE(log 2 n /log log n )

- Summary
- Metrics

Abstract

We present a deterministic algorithm running in space O(log2 n /log log n ) solving the connectivity problem on strongly unambiguous graphs. In addition, we present an O(log n ) time-bounded algorithm for this problem running on a parallel pointer machine.

Related Organizations

Rutgers University New Brunswick
United States
University of Tübingen
Germany
Rutgers, The State University of New Jersey
United States

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	11
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average