Algorithme pour trouver toutes les listes de voisins à 2 sauts dans un graphique

Étant donné un graphique , où . Qu'est - ce qu'un algorithme rapide pour générer la collection de toutes les listes de quartier 2-hop de tous les nœuds .$G = (V,E)$$|V| = n$$V$

Naïvement, vous pouvez le faire en . Avec la puissance des matrices, vous pouvez le faire avec utilisant l'algorithme de Strassen. Vous pouvez faire mieux que cela en utilisant un autre algorithme de multiplication matricielle. Une meilleure méthode? Un algorithme de Las Vegas?$O(n^3)$$O(n^{2.8})$

La question dépend vraiment de la définition précise d'un 2-hop. Si par 2 sauts vous voulez dire l'ensemble

Pourquoi? Pour chaque sommet$v$ vérifier si $v$ est adjacent au sommet $hp(v).$Si tel est le cas, vous avez trouvé un triangle dans votre graphique. De plus le graphe est sans triangle si vous ne trouvez pas de sommet$v$ avec cette propriété.

L'algorithme actuellement le plus connu pour tester si un graphe est sans triangle a une complexité temporelle $O(n^{\omega}).$