Lower Bounds to Randomized Algorithms for Graph Properties.

Andrew Chi-Chih Yao

Published in: J. Comput. Syst. Sci. (1991)

Keyphrases

randomized algorithms
lower bound
graph properties
graph theoretic
upper bound
graph theory
directed graph
np hard
worst case
randomized algorithm
optimal solution
objective function
maximal cliques
constant factor
learning algorithm
pairwise
graph data
linear programming relaxation
competitive ratio