Komplexität der Klassenfindung bei der Auswahl von Einträgen in der Matrix

Question

Angenommen, ich habe auch eine Matrix mit Einträgen $x$ oder $y$, wobei die Anzahl der Zeilen = Anzahl der Spalten = $n$.Wenn ich auswählen/einkreisen möchte $n$ Einträge so, dass für jede Zeile nur genau einer eingekreist ist, für jede Spalte auch genau einer eingekreist ist und dass alle eingekreisten Einträge nur sind $x$ (Wenn es eine solche Einkreisung von Einträgen gibt), zu welcher Komplexitätsklasse gehört dies?Danke!

Answer 1

Lassen $U$ sei die Menge der Zeilen in der gegebenen Matrix und $V$ die Menge der Spalten.Für jede $x$ in der Reihe $i$ und Spalte $j$, fügen Sie eine Kante zwischen der Reihe hinzu $i$ und Spalte $j$.Sie werden eine haben (ungewichteter) zweiteiliger Graph $G=(U,V, E)$.Das Problem besteht darin, eine zu finden perfekt passend, was im Grunde dasselbe ist wie die maximale Übereinstimmung von finden $G$.

Es gibt verschiedene Algorithmen, die die maximale Kardinalitätsübereinstimmung berechnen.Zum Beispiel, Der Hopcroft-Karp-Algorithmus läuft ein $O(\max(|E|\sqrt {|V|}, |V|^2)$.

Wir können also sagen, dass die Komplexitätsklasse des Problems in der Frage liegt $O(n^{2.5})$ seit $|E|\le n^2$ Und $|V|= 2n$.