@Article{RV76a,
author = { Ronald L. Rivest and Jean Vuillemin },
title = { On the time required to recognize properties of graphs from their
adjacency matrices },
journal = { Ast\'{e}risque },
OPTyear = { 1976 },
date = { 1976 },
volume = { 38--39 },
pages = { 213--227 },
publisher = { Soci\'{e}t\'{e} Math\'{e}matique de France },
abstract = {
Let $P$ be any non-trivial monotone property which applies to the
class of $v$-vertex graphs. We show that, if graphs are represented
by adjacency matrices, any algorithm for deciding if $P$ holds or not
of a given graph must, in the worst case, take time proportional to
$v^2$. This provides a positive answer to the question raised by
Aanderaa and Rosenberg in [5].
},
}