文章基本信息

标题：Embedding Algorithm among Half Pancake, Pancake, and Star Graphs
本地全文：下载
作者：Jung-hyun Seo ; HyeongOk Lee
期刊名称：International Journal of Software Engineering and Its Applications
印刷版ISSN：1738-9984
出版年度：2016
卷号：10
期号：3
页码：191-204
DOI：10.14257/ijseia.2016.10.3.17
出版社：SERSC
摘要：The star graph is an attractive alternative to hypercube. The pancake graph has n! nodes and generates edge using exchange of a symbol that composes a node address like star graph. The half pancake graph is a new network where the network cost of pancake graph is reduced by half. We suggest embedding algorithm among these networks. The half pancake HP n was embedded on pancake P n with dilation 1 and congestion 1. The half pancake P n was embedded on star graph S n with dilation 1.5n-2, average dilation about 0.25n+4, and congestion 6. The pancake P n was embedded on star graph S n with dilation 1.5n. All the three of embedding were one-to-one embedding with expansion 1.
关键词：interconnection network; pancake graph; star graph; half pancake graph; ; embedding algorithm