Finding Simplicial vertices in a graph.

From: Abi (abi_k--cut-here--_at_myrealbox.com)
Date: 07/02/04 

Date: Fri, 02 Jul 2004 21:20:30 +0530

A simplicial vertex in a graph is a vertex whose neighbourhood is a
clique. Are there better than O(n^3) randomized algorithms for finding
a simplicial vertex? It can be solved using matrix multiplication
algorithms in a deterministic way in O(n^2.3). But I'd like to know,
if there are any randomized algorithms for this problem that perform
better than O(n^3).
bye
abi