개발일지

Algorithm in A..Z - Minimum Vertex Cover 본문

Algorithm (알고리즘)

Algorithm in A..Z - Minimum Vertex Cover

강태종 2020. 12. 4. 20:45

개념

그래프 G에서 정점들의 집합을 S라고 할 때 S의 부분집합 'S로 모든 간선을 포함하면 이를 Vertex Cover라고 한다.

Minimum Vertex Cover는 NP지만 이분 그래프에서 Minimun Vertex Cover는 최대 매칭과 동치이다.

작동 원리

콰닉의 정리

 

Kőnig's theorem (graph theory) - Wikipedia

An example of a bipartite graph, with a maximum matching (blue) and minimum vertex cover (red) both of size six. In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum match

en.wikipedia.org

시간 복잡도

O(V^(1/2) * E)

 

저작자표시

'Algorithm (알고리즘)' 카테고리의 다른 글

Algorithm in A..Z - Network Flow  (0) 2020.12.05
Algorithm in A..Z - Maximum Independent Set  (0) 2020.12.04
Algorithm in A..Z - SPFA  (0) 2020.12.03
Algorithm in A..Z - MST (Prim)  (0) 2020.12.01
Algorithm in A..Z - Dijkstra  (0) 2020.12.01
'Algorithm (알고리즘)' Related Articles more
Comments