http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
성경아(Kyoung-A Seong),좌경룡(Kyoung-Yong Chwa),이광형(H. Lee-Kwang) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.2
The routing problem in the computer communication network is to determine a routing paih from a source to a destination node We are especially concerned for algorithm with the smallest communication cost. If communication cost is a length of the path, this problem will be the shorthest path problem in the connected graph. FLBH_N(1, h) network is a double loop network with N nodes, such that each node has a forward link connecting to its neighbor and a backward link connecting to a node a some distance h where h is called the long hop length. In this paper, we first characienze properties of the shoribest path and the struchire of FLBH_N(1, h) networks Then we divide the FLBH_N(1, h) networks into several levels using the properties Second, we present and optimal shorthest path algorithm for FLBH_N(1, h) networks with O(log h) time and O(log h) space complexity.
직사각형의 둘레에 주어진 점들에 대한 최소 갯수의 Via를 갖는 직교 Steiner 트리를 구하는 알고리즘
최윤경(Yoon Kyoung Choi),좌경룡(Kyung-Yong Chwa) 한국정보과학회 1989 한국정보과학회 학술발표논문집 Vol.16 No.1
Rectilinear Steiner tree는 평면 상에 주어진 점들을 수평선분 또는 수직선분만을 이용하여 연결하는 트리이며, 수평선분과 수직선분이 만나 연결되는 점을 via라 부른다. 본 논문에서는 직사각형의 둘레에 주어진 n개의 점에 대한 rectilinear Steiner tree 중, 첫째 목표로 최소 갯수의 via를 가지며 둘째 목표로 최단 길이를 갖는 트리를 구하는 알고리즘을 제시한다. 이러한 트리를 구하는 문제는 이중 layer 직접 회로에서의 배선에 응용될 수 있다. 본 논문에서는 이 문제의 해결을 위하여 동적 계획법을 적용한 O(n) 시간 알고리즘을 제시한다.