Conteggio a triangolo nel grafo non orientato - algoritmo, grafico, complessità temporale, conteggio dei triangoli

L'ho chiesto in un'intervista e mi è stato detto che O (n ^ 2) è possibile. Qualcuno ha un approccio semplice per questo?

Ho trovato qui un documento che mi dice che è difficile come la moltiplicazione della matrice: http://kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf

risposte:

http://en.wikipedia.org/wiki/Triangle-free_graph

Verificare se un grafico è privo di triangoli sarebbe risolto da una soluzione per quel problema. O (n ^ 2) avrebbe dovuto essere un errore dal lato degli intervistatori.

Limite inferiore dichiarato per l'algoritmo di elenco dei triangoliè O (n ^ 3) o O (m ^ 1.5), qui n è il numero di vertici e m è il numero di spigoli. Se si desidera risolvere il conteggio dei triangoli con il metodo di moltiplicazione della matrice, la complessità temporale è la stessa di moltiplicazione della matrice.

Dovresti elencare più dettagli della tua domanda. Forse il grafico ha qualche proprietà speciale.