3D Matching

2020-1학기, 대학에서 ‘알고리즘’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

---

포스트를 앞에서부터 천천히 따라왔다면, Network Flow 챕터에서 Network Flow 알고리즘을 통해 Bipartite Matching(이분 매칭) 문제를 해결할 수 있음을 공부했을 것이다.

Problem. Bipartite Matching Problem

Given $n$ boys and $n$ girls, and the compatibility btw them, find as many disjoint couples as possible.

이번에는 (boy, girl)의 쌍(pair)가 아니라 (boy, girl, pet)의 triplet에서의 Matching을 찾는 3D Matching 문제를 살펴보자!

Problem. Bipartite Matching Problem

Given $n$ boys and $n$ girls, and the compatibility btw them, find as many disjoint couples as possible.

---

추후에 환원(reduction)을 부분에서 3D Matching 문제를 다른 NP 문제로 환원하는 방법에 대해 살펴볼 예정이다.

함께보기

• Bipartite Matching
• P and NP