다른 명령
편집 요약 없음 |
잔글 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +) |
||
| 1번째 줄: | 1번째 줄: | ||
[[분류:알고리즘 설계와 분석]] | [[분류:알고리즘 설계와 분석]] | ||
상위 문서: [[알고리즘 설계와 분석#문제/알고리즘|알고리즘 설계와 분석]] | 상위 문서: [[알고리즘 설계와 분석#문제/알고리즘|알고리즘 설계와 분석]] | ||
2026년 1월 15일 (목) 15:21 기준 최신판
상위 문서: 알고리즘 설계와 분석
개요
Independent Set 문제는 아래와 같은 정의를 가진다.
입력: 그래프 [math]\displaystyle{ G=(V,E) }[/math], 정수 [math]\displaystyle{ j }[/math] 질문: 서로 연결되지 않은 [math]\displaystyle{ j }[/math]개의 정점을 포함하는 집합이 존재하는가?
해당 문제는 Independent Set의 complement(여집합)가 Vertex Cover라는 사실을 이용하여 NP-Complete임을 증명할 수 있다.