5
Dato è un grafico bipartito e vogliamo elencare tutto il grafico secondario bipartito completo massimale.Trova tutto il sottografo bipartito completo massimale dal dato grafico bipartito
Ad esempio,
insieme dei vertici L = {A, B, C, D}
insieme dei vertici R = {a, b, c, d, e}
bordi: Aa , Ab, Ba, Bb, Cc, Cd, Dc, Dd, De
La massima completa bipartita sono:
{a, B} - {a, b}
{C, D} - {c, d}
{D} - {c, d, e}
ho trovato un algoritmo di forza bruta, O (2^n). Non so se un algoritmo di approssimazione o un algoritmo randomizzato.
Questo problema è NP-completo. La questione dei metodi approssimati è meglio posta in una comunità di matematica o di CS teorica, non in una orientata alla programmazione. –
Scusa, ma pubblico lo stesso thread sulla comunità di matematica, ma hanno suggerito qui. – ColinBinWang