Independent Set 문서 원본 보기

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

==개요==
Independent Set 문제는 아래와 같은 정의를 가진다.
 입력: 그래프 <math>G=(V,E)</math>, 정수 <math>j</math>
 질문: 서로 연결되지 않은 <math>j</math>개의 정점을 포함하는 집합이 존재하는가?
해당 문제는 Independent Set의 complement(여집합)가 [[Vertex Cover]]라는 사실을 이용하여 NP-Complete임을 증명할 수 있다. 

==각주==