Popular matching is a matching that no majority vote can force a migration to another matching. Given a bipartite graph $G = (\mathcal{A} \cup \mathcal{B}, E)$ where each vertex has a strict order of preference on its neighbors and a popular matching $\mathcal{M}$ of $G$, we propose two dynamic algorithms that maintains the popular matching when a vertex is added or deleted, and when a vertex changes its preference list. We also prove that the lower bound of the dynamic popular matching problem is linear. The worst-case time complexity of our first algorithm is $O(d*(n+m))$, where $n$ is the number of vertices, $m$ is the number of edges, and $d$ is the degree of the vertex that is involved in the graph change. The second algorithm runs in $O(n+m)$. It is the first attempt to extend the two-sided popular matching problem to the dynamic environment.
인기 매칭(popular matching)은 다수결의 원칙에 의한 투표로는 다른 매칭으로의 전환을 강제할 수 없는 매칭을 말한다. 어떤 이분그래프(bipartite graph) $G = (\mathcal{A} \cup \mathcal{B}, E)$와 이 그래프 상의 각각의 노드에 자신의 이웃에 대한 엄격한 선호도 리스트가 주어질 때, 본 논문에서는 그래프의 동적인 변화 - 새로운 노드 추가, 기존 노드 삭제, 그리고 기존 노드의 선호도 변화 - 에 대응하여 인기 매칭을 유지할 수 있는 두 가지 알고리즘을 제시한다. 또한, 이러한 동적인 인기 매칭 문제 해결 알고리즘의 하한(lower bound) 시간복잡도가 그래프의 크기에 선형 비례함을 보인다. 노드의 개수를 $n$, 간선의 개수를 $m$ 이라고 하였을 때, 두 가지 알고리즘 중 첫 째 알고리즘의 경우 $O(d*(n+m))$의 시간복잡도를 가지고 이 때 $d$는 그래프에 변화를 일으키는 노드의 이웃 개수이다. 두 번째 알고리즘은 $O(n+m)$의 시간복잡도를 가진다. 본 논문은 양쪽 인기 매칭 문제(two-sided popular matching problem)을 동적인 환경으로 확장하는 첫 번째 시도이다.
