Brute Force在二分圖中尋找最大獨立頂點集的算法？

Question

有沒有人知道蠻力算法的通用輪廓在二分圖中找到最大獨立頂點集？

我知道還有其他算法，例如König定理，用於查找MIS，但是我想知道蠻力方法的僞代碼是什麼？

另外，這種蠻力算法的運行時間複雜度是多少？

Answer 1

蠻力算法只是遍歷所有頂點集合，並檢查它們是否是獨立的。有2^n頂點集和遍歷所有邊檢查獨立性是O(m)，所以這個成本O(2^n*m)。