| 1 |
1
온라인 그래프 매칭 장치에 의한 온라인 그래프 매칭 방법에 있어서,정점(vertex) 또는 에지(edge)로 정의되는 개체에 대한 정보를 수신하는 단계;상기 수신된 개체를 포함하고 제한조건을 만족하는 증가 경로(augmenting path) 중에서 하나의 증가 경로를 선택하는 단계; 및상기 선택된 증가 경로가 있으면 상기 증가 경로를 따라 에지를 넣고 빼는 매칭 증가를 수행하거나, 상기 선택된 증가 경로가 없으면 매칭 증가를 수행하지 않는 매칭 단계를 포함하는 온라인 그래프 매칭 방법
|
| 2 |
2
제1항에 있어서,상기 제한조건은 상기 증가 경로의 길이가 재할당 개수에 대한 제한 예산(k)-1 보다 짧거나 동일한 것으로 정의되는 것을 특징으로 하는 온라인 그래프 매칭 방법
|
| 3 |
3
제2항에 있어서,상기 제한 예산은 실제 예산보다 더 작은 것으로 간주되는 것을 특징으로 하는 온라인 그래프 매칭 방법
|
| 4 |
4
제1항 내지 제3항 중 어느 한 항에 있어서,상기 하나의 증가 경로를 선택하는 단계는 가장 짧은 경로를 선택하거나 가중치에 따른 가장 이익이 되는 증가 경로를 선택하는 것을 특징으로 하는 온라인 그래프 매칭 방법
|
| 5 |
5
제1항 내지 제4항 중 어느 한 항에 있어서,(i) 재할당 개수에 대한 제한 예산 k를 갖는 상기 정점의 수신에 따른 최대 카디널리티 온라인 매칭 문제(maximum-cardinality online matching problem under vertex arrivals)에 대해서 상기 k로 표현된 경쟁비로 해를 제공하거나,(ii) 재할당 개수에 대한 제한 예산 k를 갖는 상기 에지의 수신에 따른 최대 카디널리티 온라인 매칭 문제(maximum-cardinality online matching problem under edge arrivals)에 대해서 상기 k로 표현된 경쟁비로 해를 제공하거나,(iii) 재할당 개수에 대한 제한 예산을 갖는 상기 정점의 수신에 따른 최대 가중치 온라인 이분 왼쪽 완벽 매칭 문제(maximum-weight online bipartite left-perfect matching problem under vertex arrivals)에 대해서 특정 경쟁비로 해를 제공하는 것을 특징으로 하는 온라인 그래프 매칭 방법
|
