http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
에지 고장이 있는 Restricted Hypercube-Like 그래프의 해밀톤 경로
김숙연,전병태,Kim, Sook-Yeon,Chun, Byung-Tae 한국정보처리학회 2011 정보처리학회논문지 A Vol.18 No.6
Restricted Hypercube-Like(RHL) 그래프는 교차큐브, 뫼비우스큐브, 엠큐브, 꼬인큐브, 지역꼬인큐브, 다중꼬인큐브, 일반꼬인큐브와 같이 유용한 상호연결망들을 광범위하게 포함하는 그래프군이다. 본 논문에서는 $m{\geq}4$ 인 m-차원 RHL 그래프 G에 대해서 임의의 에지 집합 $F{\subset}E(G)$, ${\mid}F{\mid}{\leq}m-2$, 가 고장일 때, 고장 에지들을 제거한 그래프 $G{\setminus}F$는 임의의 서로 다른 두 정점 s와 t에 대해서 dist(s, V(F))${\neq}1$ 이거나 dist(t, V(F))${\neq}1$이면 해밀톤 경로가 있음을 보인다. V(F)는 F에 속하는 에지들의 양 끝점들의 집합이고 dist(v, V(F))는 정점 v와 집합 V(F)의 정점들 간의 최소 거리이다. Restricted Hypercube-Like (RHL) graphs are a graph class that widely includes useful interconnection networks such as crossed cube, Mobius cube, Mcube, twisted cube, locally twisted cube, multiply twisted cube, and generalized twisted cube. In this paper, we show that for an m-dimensional RHL graph G, $m{\geq}4$, with an arbitrary faulty edge set $F{\subset}E(G)$, ${\mid}F{\mid}{\leq}m-2$, graph $G{\setminus}F$ has a hamiltonian path between any distinct two nodes s and t if dist(s, V(F))${\neq}1$ or dist(t, V(F))${\neq}1$. Graph $G{\setminus}F$ is the graph G whose faulty edges are removed. Set V(F) is the end vertex set of the edges in F and dist(v, V(F)) is the minimum distance between vertex v and the vertices in V(F).
꼬인 큐브 토러스: 3차원 꼬인 큐브에 기반한 새로운 토러스 상호연결망
김종석,이형옥,김성원,Kim, Jong-Seok,Lee, Hyeong-Ok,Kim, Sung-Won 한국정보처리학회 2011 정보처리학회논문지 A Vol.18 No.5
본 논문은 널리 알려진 3차원 꼬인 큐브를 기반으로 하는 새로운 상호연결망 꼬인 큐브 토러스(TT) 네트워크를 제안한다. 꼬인 큐브 토러스 네트워크는 동일한 노드수를 갖는 honeycomb 토러스보다 짧은 지름을 갖고, 망 비용이 개선된 연결망이다. 본 논문에서는 꼬인 큐브 토러스의 라우팅 알고리즘을 제안하고, 지름, 망 비용, 이분할에지수, 해밀토니안 사이클을 분석한다. We propose a new interconnection network, called Twisted cube torus(TT) network based on well-known 3-dimensional twisted cube. Twisted cube torus network has smaller diameter and improved network cost than honeycomb torus with the same number of nodes. In this paper, we propose routing algorithm of Twisted cube torus network and analyze its diameter, network cost, bisection width and hamiltonian cycle.
크기 2<sup>n</sup> ×2<sup>m</sup>인 메쉬의 꼬인 큐브에 대한 임베딩
김숙연,Kim, Sook-Yeon 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.4
The twisted cube has received great attention as an interconnection network of parallel systems because it has several superior properties, especially in diameter, to the hypercube. It was recently known that, for even m, a mesh of size $2{\times}2^m$ can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size $4{\times}2^m$ with dilation 1 and expansion 2 [Lai and Tsai, 2008]. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a twisted cube with dilation 1. In this paper, we show that a mesh of size $2^n{\times}2^m$ can be embedded into a twisted cube with dilation 1 and expansion $2^{n-1}$ for even m and with dilation 1 and expansion $2^n$ for odd m where $1{\leq}n{\leq}m$. 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지는 꼬인 큐브는 병렬처리 시스템의 상호연결망으로 각광 받아 왔다. 짝수인 m 에 대하여 크기가 $2{\times}2^m$인 메쉬가 연장률 1과 확장율 1로, 혹은 크기가 $4{\times}2^m$인 메쉬가 연장율 1과 확장율 2로 꼬인 큐브에 임베딩됨은 최근에 알려졌다 [Lai and Tsai, 2008]. 그러나 양변의 길이가 모두 8 이상인 메쉬가 꼬인 큐브에 연장율 1로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 m 이 짝수일 경우엔 크기 $2^n{\times}2^m$인 메쉬가 꼬인 큐브에 연장율 1, 확장율 $2^{n-1}$ 로 임베딩됨을 보이고 m이 홀수일 경우엔 연장율 1, 확장율 $2^n$로 임베딩됨을 보인다 ($1{\leq}n{\leq}m$).
김숙연(Sook-Yeon Kim) 한국정보과학회 2010 정보과학회논문지 : 시스템 및 이론 Vol.37 No.2
꼬인 큐브는 병렬처리 시스템의 상호연결망으로서 널리 알려진 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지므로 각광받아 왔다. 본 논문에서는 크기 2ⁿ×2<SUP>m</SUP>인 메쉬의 복사본 2ⁿ?¹ 개가 꼬인 큐브에 노드 중복없이 연장율 1로 임베딩될 수 있음을 보인다(1≤n≤m). 여기서 확장율은 m이 짝수이면 1이고 홀수이면 2이다. The twisted cube has received great attention because it has several superior properties to the hypercube that is widely known as a versatile parallel processing system. In this paper, we show that node-disjoint 2ⁿ?¹ meshes of size 2ⁿ×2<SUP>m</SUP> can be embedded into a twisted cube with dilation 1 where 1≤n≤m. The expansion is 1 for even m and 2 for odd m.
김숙연 한국정보처리학회 2009 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.16 No.4
The twisted cube has received great attention as an interconnection network of parallel systems because it has several superior properties, especially in diameter, to the hypercube. It was recently known that, for even , a mesh of size 2×2m can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size 2×2m with dilation 1 and expansion 2 [Lai and Tsai, 2008]. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a twisted cube with dilation 1. In this paper, we show that a mesh of size 2n×2m can be embedded into a twisted cube with dilation 1 and expansion 2n-1 for even m and with dilation 1 and expansion 2n for odd where 1≤n≤m. 하이퍼큐브와 많은 면에서 비슷하면서도 절반 정도의 지름을 가지는 등 개선된 망 성질들을 가지는 꼬인 큐브는 병렬처리 시스템의 상호연결망으로 각광 받아 왔다. 짝수인 m에 대하여 크기가 2n×2n 인 메쉬가 연장률 1과 확장율 1로, 혹은 크기가 4×2m인 메쉬가 연장율 과 확장율 2로 꼬인 큐브에 임베딩됨은 최근에 알려졌다 [Lai and Tsai, 2008]. 그러나 양변의 길이가 모두 8 이상인 메쉬가 꼬인 큐브에 연장율 로 임베딩되는지는 알려진 바가 없다. 본 논문에서는 이 짝수일 경우엔 크기 2n×2m 인 메쉬가 꼬인 큐브에 연장율1 , 확장율 2n-1로 임베딩됨을 보이고 이 홀수일 경우엔 연장율1 , 확장율2n 로 임베딩됨을 보인다 (1≤n≤m).
김숙연 ( Sook Yeon Kim ) 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.4
The twisted cube has received great attention as an interconnection network of parallel systems because it has several superior properties, especially in diameter, to the hypercube. It was recently known that, for even m , a mesh of size 2× 2m can be embedded into a twisted cube with dilation 1 and expansion 1 and a mesh of size 4 × 2m with dilation 1 and expansion 2 [Lai and Tsai, 2008]. However, as we know, it has been a conjecture that a mesh with more than eight rows and columns can be embedded into a twisted cube with dilation 1. In this paper, we show that a mesh of size 2ⁿ × 2m can be embedded into a twisted cube with dilation 1 and expansion 2n?1 for even m and with dilation 1 and expansion 2n for odd m where 1≤ n ≤ m.