Vertex Cover 문서 원본 보기

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]] 

==개요==
==Vertex Cover==
Vertex Cover 문제는 아래와 같은 정의를 가진다. 
 입력: 그래프 <math>G=(V,E)</math>, 정수 <math>k</math>
 질문: 최대 <math>k</math>개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가?
해당 문제는 3-SAT <math> \rightarrow</math> Vertex Cover reduction을 통해서 Vertex Cover가 NP-Complete임을 보일 수 있다.
이때 Vertex Cover의 complement는 [[Independent Set]]이다.

==각주==