Complessità della selezione delle voci nella matrice per la ricerca delle classi

Question

Supponiamo che anch'io abbia una matrice con voci $x$ O $y$, dove il numero di righe = numero di colonne = $n$.Se voglio selezionare/cerchiare $n$ voci tali che per ogni riga ne sia cerchiata esattamente una, per ogni colonna ne sia cerchiata esattamente una e che tutte le voci cerchiate siano solo $x$ (se esiste un tale circolo di voci), a quale classe di complessità appartiene?Grazie!

Answer 1

Permettere $U$ essere l'insieme di righe nella matrice data e $V$ l'insieme delle colonne.Per ciascuno $x$ alla fila $i$ e colonna $j$, aggiungi un bordo tra le righe $i$ e colonna $j$.Avrai un Grafico bipartito (non ponderato). $G=(U,V, E)$.Il problema è trovare un abbinamento perfetto, che equivale sostanzialmente a trovare la corrispondenza massima di $G$.

Ce ne sono vari algoritmi che calcolano la corrispondenza della cardinalità massima.Per esempio, L'algoritmo di Hopcroft-Karp corre dentro $O(\max(|E|\sqrt {|V|}, |V|^2)$.

Quindi, possiamo dire che la classe di complessità del problema nella domanda è in $O(n^{2.5})$ Da $|E|\le n^2$ E $|V|= 2n$.