Questions marquées «graph-algorithms»

Il est connu que Ford-Fulkerson ou Edmonds-Karp avec l'heuristique fat pipe (deux algorithmes pour max-flow) ne doivent pas s'arrêter si certains des poids sont irrationnels. En fait, ils peuvent même converger vers la mauvaise valeur! Cependant, tous les exemples que j'ai pu trouver dans la...

Soit G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2}) un graphe aléatoire sur ≈n3/2≈n3/2\approx n^{3/2} bords. Avec une probabilité très élevée, GGG a de nombreux cycles à 444 cycles. Notre objectif est de produire l'un de ces 444 cycles le plus rapidement possible. Supposons que nous ayons accès à...