کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430053 687788 2013 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Multiswapped networks and their topological and algorithmic properties
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Multiswapped networks and their topological and algorithmic properties
چکیده انگلیسی


• We define multiswapped networks to extend the range of potential hybrid optoelectronic/electronic interconnection networks.
• We derive a structural properties of multiswapped networks in terms of these properties of its two constituent component graphs.
• We develop a deterministic multipath source routing algorithm for our multiswapped network.

We generalise the biswapped network Bsw(G)Bsw(G) to obtain a multiswapped network Msw(H;G)Msw(H;G), built around two graphs G and H  . We show that the network Msw(H;G)Msw(H;G) lends itself to optoelectronic implementation and examine its topological and algorithmic. We derive the length of a shortest path joining any two vertices in Msw(H;G)Msw(H;G) and consequently a formula for the diameter. We show that if G   has connectivity κ⩾1κ⩾1 and H   has connectivity λ⩾1λ⩾1 where λ⩽κλ⩽κ then Msw(H;G)Msw(H;G) has connectivity at least κ+λκ+λ, and we derive upper bounds on the (κ+λ)(κ+λ)-diameter of Msw(H;G)Msw(H;G). Our analysis yields distributed routing algorithms for a distributed-memory multiprocessor whose underlying topology is Msw(H;G)Msw(H;G). We also prove that if G and H   are Cayley graphs then Msw(H;G)Msw(H;G) need not be a Cayley graph, but when H   is a bipartite Cayley graph then Msw(H;G)Msw(H;G) is necessarily a Cayley graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 79, Issue 8, December 2013, Pages 1269–1286
نویسندگان
,