유향 사이클 그래프의 에지 집합으로부터 사이클 정점 순서를 찾는 효율적인 RMESH 알고리즘

김수환 · 2014

본 논문에서는 유향 사이클 그래프의 에지 집합으로부터 사이클을 구성하는 정점들의 순서를 재구성가능한 메쉬(RMESH)에서 찾는 문제를 고려한다. 이 문제는 순차 알고리즘으로 선형 시간에 해결되는 문제이지만 선형 시간보다 낮은 차수의 재구성가능한 메쉬 알고리즘을 고안하는 것은 정점 순서가 가지는 순차성 때문에 단순하지 않다. 평면 상의 모든 다각형은 유향 사이클 그래프에 해당하기 때문에, 이 문제에 대한 해는 다각형의 정점별 이웃 정보로부터 다각형을 구성해야 하는 문제를 해결하는데 활용될 수 있다. 기존 연구로서 n개의 에지를 가진 유향 사이클 그래프의 사이클 정점 순서를 n×n 2 RMESH에서 상수 시간에 찾는 알고리즘이 나와 있다. 본 논문에서는 n×n RMESH에서 사이클 정점 순서를 O(log 2 n) 시간에 찾는 알고리즘을 제시한다. 이 알고리즘은 기존의 결과에 비해 병렬 알고리즘의 비용을 나타내는 프로세서-시간 곱 지표를 O(n 3 )에서 O(n 2 log 2 n) 으로 개선한다.

Cited by 1 works.

Authors

References