초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

In the field of interconnection networks, star graphs have been presented as an alternative to hypercube. The star graph has n! Nodes and the node address is represented by a permutation of n natural numbers. A node of the star graph can exchange with the first symbol and one of the remaining symbol...

In the field of interconnection networks, star graphs have been presented as an alternative to hypercube. The star graph has n! Nodes and the node address is represented by a permutation of n natural numbers. A node of the star graph can exchange with the first symbol and one of the remaining symbols. Therefore, the degree is n-1. The Bubblesort graph is a network of star graph classes with n! Nodes and nodes can exchange two neighboring symbols. Therefore, the degree is n-1. The half-bubblesort graph is a new graph that reduces the n-1 degree of the bubblesort graph by half. If both graphs have the same number of nodes n!, the network cost is about half. When the graph is newly designed, it is necessary to develop various algorithms that can be realized in the designed graph. Embedding maps arbitrary graphs to different graphs. The graph consists of nodes and edges. In embedding, a node maps to a node, and an edge maps to a path. As a representative evaluation scale, there is an dilation, expansion and congestion. In this paper, a half-bubblesort graph is embedded in the star graph at an dilation of 1.5n-2, a congestion of 3, and an expansion of 1.

Keyword