Lower bounds to randomized algorithms for graph properties

DOI10.1016/0022-0000(91)90003-NzbMath0732.68058OpenAlexW2146111707WikidataQ56701669 ScholiaQ56701669MaRDI QIDQ808708

Andrew Chi-Chih Yao

Publication date: 1991

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(91)90003-n

zbMATH Keywords

randomized algorithmn-vertex graphsnontrivial monotone graph property

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Lower bounds on probabilistic linear decision trees
• On recognizing graph properties from adjacency matrices
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees

This page was built for publication: Lower bounds to randomized algorithms for graph properties