구간 그래프와 순열 그래프의 최대 가중치 독립 집합을 찾는 병렬 알고리즘
김춘수, 김주리, 장직현 · 한국정보과학회 학술발표논문집 · 1995
구간 그래프와 순열 그래프에서 최근에 제안된 최대 가중치 독립 집합을 계산하는 병렬 알고리즘은 CREW PRAM 모델에서 O(n³/logn) 프로세서를 사용하여 O(log²n)의 시간복잡도를 갖는다. 본 논문은 같은 문제에 대해 CREW PRAM 모델보다 병렬성이 약한 EREW PRAM 모델상에서 수행되는 병렬 알고리즘을 제안한다. 우리가 제안하는 알고리즘은 분할 정복 방식을 기초로 하며, 최근 결과와 같은 복잡도를 갖는다.
Cited by 0 works.