Improved lower bounds for the cycle detection problem
type: Item
instance of: scholarly article
title: Improved lower bounds for the cycle detection problem
zbMATH Open document ID: 0565.68042
DOI: 10.1016/0304-3975(85)90044-1
author: Eric Allender
author: Maria M. Klawe
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: Lower bounds for the 'cycle detection problem' were recently investigated by \textit{F. E. Fich} [J. Comput. Syst. Sci. 26, 392-409 (1983; Zbl 0509.68040)]. She showed that Floyd's algorithm was optimal among those algorithms which have \(M=2\) memory locations and which make a finite number of 'jumps'. A lower bound for the case where \(M>2\) was also presented, but the question of whether having more than two memory locations could actually yield a better algorithm was left open. In this report, we show that it cannot. A lower bound was also presented by Fich [loc. cit.] for algorithms which have two memory locations and which make a finite number of 'back advances'. We show here that the same lower bound holds even if the restriction on back advances is dropped.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3902035
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90044-1
OpenAlex ID: W2022952433
Wikidata QID: Q56388141
cites work: An improved Monte Carlo factorization algorithm
cites work: Lower bounds for the cycle detection problem
cites work: Q5585021
cites work: The Complexity of Finding Cycles in Periodic Functions
description: scientific article; zbMATH DE number 3902035