Vertex Cover: 두 판 사이의 차이

2025년 12월 1일 (월) 16:46 기준 최신판

Vertex Cover 문제는 아래와 같은 정의를 가진다.

입력: 그래프  $G = (V, E)$ , 정수  $k$ 
질문: 최대  $k$ 개의 정점만 선택해서 모든 간선이 적어도 하나의 선택된 정점에 닿도록 만들 수 있는가?

해당 문제는 3-SAT $\to$ Vertex Cover reduction을 통해서 Vertex Cover가 NP-Complete임을 보일 수 있다. 이때 Vertex Cover의 complement는 Independent Set이다.

@@ 1번째 줄: / 1번째 줄: @@
 [[분류:알고리즘 설계와 분석]]
 [[분류:컴퓨터 공학]]
-상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]]
+상위 문서: [[알고리즘 설계와 분석#문제/알고리즘|알고리즘 설계와 분석]]
 ==개요==