10. 25

• domination에 관련한 굉장히 깔끔하게 정리된 사이트를 발견했다. wow..
• 예전 KTU camp Day5의 <Reordering Ones>문제는 결국 Biclique를 구하는 문제였는데, 이건 결국 complement graph상에서의 maximum independent set을 구하는 문제로 변환이 가능하다! 이건 König's Theorem에 따라 bipartite graph가 perfect하고, perfect한 그래프는 그것의 complement도 perfect하기 때문에 maximum clique를 쉽게 구할 수 있는 것.
• 
• minimum vertex cover를 구하는 알고리즘 = 반전시키면 maximum independent set을 구하는 알고리즘도 새롭게 알았다. 엣지들에 방향성을 부여해서, 매칭에 포함된 간선은 오른쪽으로, 그렇지 않은 간선은 왼쪽으로 두고 매칭되지 않은 정점으로부터 출발해서 DFS를 돌린다. 여기서 방문되지 않은 왼쪽 원소와, 방문된 오른쪽 원소가 minimum vertex cover가 된다.