본문 바로가기

추천 검색어

실시간 인기 검색어

학술논문

하프 버블정렬 그래프를 스타 그래프에 임베딩

이용수 31

영문명
Embedding algorithm Half Bubblesort Graph in Star Graph
발행기관
인문사회과학기술융합학회
저자명
서정현(Jung-Hyun Seo) 이형옥(HyeongOk Lee)
간행물 정보
『예술인문사회융합멀티미디어논문지』8권 9호, 211~219쪽, 전체 9쪽
주제분류
사회과학 > 사회과학일반
파일형태
PDF
발행일자
2018.09.30
4,000

구매일시로부터 72시간 이내에 다운로드 가능합니다.
이 학술논문 정보는 (주)교보문고와 각 발행기관 사이에 저작물 이용 계약이 체결된 것으로, 교보문고를 통해 제공되고 있습니다.

1:1 문의
논문 표지

국문 초록

상호연결망 분야에서 스타 그래프는 하이퍼큐브의 대안으로 발표되었다. 스타 그래프는 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.

목차

1. 서론
2. 관련연구
3. 임베딩 알고리즘
4. 결론

키워드

해당간행물 수록 논문

참고문헌

교보eBook 첫 방문을 환영 합니다!

신규가입 혜택 지급이 완료 되었습니다.

바로 사용 가능한 교보e캐시 1,000원 (유효기간 7일)
지금 바로 교보eBook의 다양한 콘텐츠를 이용해 보세요!

교보e캐시 1,000원
TOP
인용하기
APA

서정현(Jung-Hyun Seo),이형옥(HyeongOk Lee). (2018).하프 버블정렬 그래프를 스타 그래프에 임베딩. 예술인문사회융합멀티미디어논문지, 8 (9), 211-219

MLA

서정현(Jung-Hyun Seo),이형옥(HyeongOk Lee). "하프 버블정렬 그래프를 스타 그래프에 임베딩." 예술인문사회융합멀티미디어논문지, 8.9(2018): 211-219

결제완료
e캐시 원 결제 계속 하시겠습니까?
교보 e캐시 간편 결제