Giugno 2018 Archive

Dato un grafo orientato e pesato G=(V, E) con pesi positivi, cioè w(u, v) > 0 per ogni (u, v) ∈ E, si vuole determinare se esiste in G un ciclo c ≡ <x₀, x₁, ... x_q> (con x₀ = x_q) per cui sia soddisfatta la seguente condizione:

$\underset{i=1}{\overset{q}{\Pi }}2w{\left(x_{i=1},x_i\right)}^3>2^q$

Si sviluppi un algoritmo per risolvere questo problema, se ne discuta la correttezza e si determini la sua complessità computazionale. (Suggerimento: si cerchi di ricondurre il problema dato ad uno noto)