类的复杂性寻找矩阵中的条目选择

Question

假设我有一个带有条目的矩阵 $ x $ 或 $ y $ ，其中数字Rows=列数= $ n $ 。如果我想选择/ circle $ n $ 条目，例如对于每一行，只有一个被旋转的，对于每列来说，每个列都恰好旋转，这样卷曲的所有条目都仅为 $ x $ （如果存在这样的圆圈存在），则哪些复杂性类属于？谢谢！

Answer 1

let $ u $ 是给定矩阵中的行集和 $ v $ 该集合列。对于每个 $ x $ 在行 $ i $ 和列 $ j $ ，在行 $ i $ 和列 $ j $ 。您将拥有一个（未加权）二角形图 $ g=（u，v，e）$ 。问题是找到一个完美匹配，它基本上与查找相同 $ g $ 的最大匹配。

有各种计算匹配的最大基数匹配。例如， hopcroft-karp算法在 $ O（\ max（| e | \ sqrt {| v |}，| v | ^ 2）$ 。

所以，我们可以说问题中问题的复杂性类别在 $ o（n ^ {2.5}）$ 以来，因为 $ | e | \ le n ^ 2 $ 和 $ | v |= 2n $ 。