@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]. }, }