An Average Case NP-complete Graph Problem

Leonid A. Levin Ramarathnam Venkatesan

Published in: CoRR (2001)

Keyphrases

average case
np complete
polynomial time complexity
bounded treewidth
worst case
np hard
randomly generated
uniform distribution
worst case analysis
learning curves
directed graph
computational complexity
vc dimension
conjunctive queries
data sets
undirected graph
graph theoretic
sample size
special case