스타 그래프와 팬케익, 버블정렬 그래프 사이의 임베딩 알고리즘

Title
스타 그래프와 팬케익, 버블정렬 그래프 사이의 임베딩 알고리즘
Other Titles
Embedding algorithm among star graph and pancake graph, bubblesort graph
Author(s)
김종석이형옥[이형옥]김성원
Keywords
Star graph; Pancake graph; Bubblesort graph; Embedding; Algorithm; 스타 그래프; 팬케익 그래프; 버블정렬 그래프; 임베딩; 알고리즘
Issue Date
201009
Publisher
한국컴퓨터교육학회
Citation
컴퓨터교육학회 논문지, v.13, no.5, pp.91 - 102
Abstract
스타 그래프는 노드 대칭성, 최대 고장 허용도, 계층적 분할 성질을 갖고, 하이퍼큐브보다 망 비용이 개선된 널리 알려진 상호 연결망이다. 본 연구에서는 스타 그래프와 그의 변형된 그래프들 상호 간의 임베딩 방법을 제안한다. 버블정렬 그래프가 팬케익 그래프와 스타 그래프에 각각 연장율 3, 확장율 1로 임베딩 가능함을 보이고, 팬케익 그래프가 버블정렬그래프에 임베딩 하는 연장율 비용이 O(n2)임을 보인다. 그리고 스타 그래프가 팬케익 그래프에 연장율 4, 확장율 1로 임베딩 가능함을 보인다. 또한 스타그래프를 버블정렬 그래프에, 팬케익 그래프를 스타 그래프에 임베딩 하는 연장율 비용이 각각 O(n)임을 보인다.
URI
http://hdl.handle.net/YU.REPOSITORY/23601
ISSN
1598-5016
Appears in Collections:
중앙도서관 > rims journal
공과대학 > 모바일정보통신공학과 > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE