کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951626 1441484 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sufficient conditions for Hamiltonicity in multiswapped networks
ترجمه فارسی عنوان
شرایط مناسب برای هملتونیتی در شبکه های چندرسانه ای
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
OTIS networks are interconnection networks amenable to deployment as hybrid networks containing both electronic and optical links. Deficiencies as regards symmetry led to the subsequent formulation of biswapped networks which were later generalized to multiswapped networks so as to still enable optoelectronic implementation (as it happens, multiswapped networks also generalize previously studied hierarchical crossed cubes). Multiswapped networks of the form Msw(H;G) are known to possess good (graph-theoretic) properties as regards their use as (optoelectronic) interconnection networks (in distributed-memory multiprocessors) and in relation to those of the component networks G and H. Combinatorially, they provide a hierarchical mechanism to define new networks from existing networks (so that the properties of the new network can be controlled in terms of the constituent networks). In this paper, we prove that if G and H are Hamiltonian networks then the multiswapped network Msw(H;G) is also Hamiltonian. At the core of our proof is finding specially designed Hamiltonian cycles in 2-dimensional and heavily pruned 3-dimensional tori, irrespective of the actual networks G and H we happen to be working with. This lends credence to the role of tori as fundamental networks within the study of interconnection networks.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 101, March 2017, Pages 17-26
نویسندگان
,