행렬스타 그래프와 하프 팬케익 그래프 사이의 일대일 사상 알고리즘 (One-to-One Mapping Algorithm between Matrix Star Graphs and Half Pancake Graphs)

서지정보

· 발행기관 : 한국지능시스템학회
· 수록지 정보 : 한국지능시스템학회 논문지 / 24권 / 4호 / 430 ~ 436페이지
· 저자명 : 김종석, 유남현, 이형옥

초록

행렬스타 그래프와 하프팬케익 그래프는 스타 그래프의 변형으로 노드 대칭성과 허용도 등 여러 가지 좋은 성질을 갖는다. 본 연구에서는 행렬스타 그래프와 하프팬케익 그래프 사이의 임베딩을 분석한다. 연구 결과로 행렬스타 그래프 MS2,n는 하프팬케익 그래프 HP2n에 연장율 5, 확장율 1에 임베딩 가능하다. 또한 하프팬케익 그래프 HP2n는 행렬스타 그래프 MS2,n에 임베딩하는 연장율 비용이 O(n)임을 보인다. 이러한 결과는 스타 그래프에서 개발된 여러 가지 알고리즘을 하프팬케익 그래프에서 상수의 추가적인 비용으로 시뮬레이션 할 수 있음을 의미한다. 왜냐하면 스타 그래프 Sn은 행렬스타 그래프 MS2,n의 부분 그래프이기 때문이다.

영어초록

Matrix-star and Half-Pancake graphs are modified versions of Star graphs, and has some good characteristics such as node symmetry and fault tolerance. This paper analyzes embedding between Matrix-star and Half-Pancake graphs. As a result, Matrix-star graphs MS2,n can be embedded into Half-Pancake graphs HP2n with dilation 5 and expansion 1. Also, Half Pancake Graphs, HP2n can be embedded into Matrix Star Graphs, MS2,n with the expansion cost, O(n). This result shows that algorithms developed from Star Graphs can be applied at Half Pancake Graphs with additional constant cost because Star Graphs, Sn is a part graph of Matrix Star Graphs, MS2,n.

참고자료

· 없음