http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
볼록 이분할 그래프에서 최대 매칭을 찾기 위한 개선된 Boolean 회로
박은희(Eunhui Park),박근수(Kunsoo Park) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.1
Boolean 회로는 parallel 알고리즘을 위한 단순하면서도 실제적인 모델이다. Chung & Lee은 Boolean 회로 모델에서 볼록 이분할 그래프를 위한 최대 매칭을 찾는 O(log²n+logn · loglogn · logb)depth와 O(bn³) size의 알고리즘을 제시하였다. 본 논문에서는 prefix computaion 및 ASCEND, odd-even-merge의 방법을 이용하여 이를 개선한 O(log²n · logb) depth, O(bn²logn) size의 최대 매칭 알고리즘을 제시한다.