http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
장정희(Jeong-Hee Jang),하경주(Kyoung-Ju Ha),김승호(Sung-Ho Kim),유관우(Kwan-Woo Ryu) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.7
본 논문에서는 직사각형내에서의 단일층 배선(one-layer routing)을 위한 최적 병렬 알고리즘을 소개한다. 직사각형의 경계에 단자(terminal)의 집합 {a₁, a₂, …, a_n}과 {b₁, b₂, …, b_n}이 주어질 때 a₁와 b₁, 1≤i≤n,를 연결하는데 모든 연결선들이 그 사각형내에 놓여 있도록 하고 배선되는 선들이 서로 교차하지 않도록 배선한다. 이 병렬 알고리즘은 CREW PRAM 모델에서 0(n/logn)개의 프로세서로 0(logn)시간에 수행되고, COMMON CRCW PRAM 모델에서는 0(nloglogn/logn)개의 프로세서로 0(logn/loglogn)시간에 수행된다. 또 EREW PRAM에서는 0(n)개의 프로세서로 0(logn)시간에 수행된다. In this paper, we present an optimal parallel algorithm for one-layer routing in a rectangle. Given two sets of terminals {a₁, a₂, …, a_n} and {b₁, b₂, …, b_n} on the boundary of a rectangle, we connect a₁ and b₁, 1≤i≤n, such that all the wires lie within the polygon and none of two wires intersect. This algorithm performs in 0(logn) time on the CREW PRAM with 0(n/logn) processors, and in 0(logn/loglogn) time on the COMMON CRCW PRAM with 0(nloglogn/logn) processors. On the EREW PRAM, this algorithm performs in 0(logn) time with 0(n) processors.