하프 버블정렬 그래프를 스타 그래프에 임베딩 (Embedding algorithm Half Bubblesort Graph in Star Graph)

서지정보

· 발행기관 : 사단법인 인문사회과학기술융합학회
· 수록지 정보 : 예술인문사회 융합 멀티미디어 논문지 / 8권 / 9호 / 211 ~ 219페이지
· 저자명 : 서정현, 이형옥

초록

상호연결망 분야에서 스타 그래프는 하이퍼큐브의 대안으로 발표되었다. 스타 그래프는 n!개의 노드를 가지며 노드 주소는 n개 자연수로 이루어진 순열로 표현된다. 스타 그래프는 노드는 첫 번째 심볼과 나머지 심볼 중 하나와 교환할 수 있다. 따라서 분지수는 n-1이다. 버블정렬 그래프는 스타 그래프 부류의 연결망으로 n!개의 노드를 가지며 노드는 이웃한 두 심볼을 교환할 수 있다. 따라서 분지수는 n-1이다. 하프 버블정렬 그래프는 버블정렬 그래프의 분지수 n-1을 절반으로 줄여 두 그래프가 같은 노드수 n!를 갖는 경우 망 비용이 약 절반인 새로운 그래프이다. 그래프가 새로 설계되면 설계된 그래프에서 실현 가능한 다양한 알고리즘 개발이 필요하다. 임베딩은 임의의 그래프를 다를 그래프에 사상하는 것이다. 그래프는 노드와 에지로 이루어져 있다. 임베딩에서 노드는 노드로 사상하고 에지는 경로로 사상한다. 대표적인 평가척도로 연장율, 밀집율 확장율이 있다. 본 논문에서는 하프버블정렬 그래프를 연장율 1.5n-2, 밀집율 3, 확장율 1에 스타 그래프에 임베딩 하였다.

영어초록

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.

참고자료

· 없음