Ernastuti, Ernastuti and Vajnovki, Vincent (2007) Embeddings Of Linear Arrays, Rings And 2D meshes On Extended lucas Cube Network. Proceedings of the International Conference on Electrical Engineering and Informatics.

Text
EMBEDDINGS OF LINIER ARRAYS_UG.PDF  Submitted Version Download (354Kb)  Preview 
Abstract
A Fibonacci string is a length ii binary string containing no two consecutive 1 s. Fibonacci cubes (FC), Extended Fibonacci cubes (ELC) and Lucas cubes (LC) are subgraphs of hvpercube defined in terms of Fibonacci strings. All these cubes were introduced in the last ten years as models for interconnection networks and shown that their network topology posseses many interesting properties that are important in parallel processor network design and parallel applications. In this paper, we propose a new family of Fibonaccilike cube, namely Extended Lucas Cube (ELC). We address the following network simulation problem : Given a linear array, a ring or a twodimensional mesh; how can its nodes be assigned to ELC nodes so as to keep their adjacent nodes near each other in ELC ?. We first show a simple fact that there is a Hamiltonian path and cycle in any ELC. We prove that any linear array and ring network can be embedded into its corresponding optimum ELC (the smallest ELC with at least the number of nodes in the ring) with dilation 1, which is optimum for most cases. Then, we describe dilation 1 embeddings of a class of meshes into their corresponding optimum ELC. Keywords: (Extended) Fibonacci cube, Extended Lucas cube, Fibonacci number, Hamiltonian path, Hamiltonian cycle, linear array, ring , mesh, network
Item Type:  Article 

Uncontrolled Keywords:  Fibonacci cube; Extended Lucas cube; Fibonacci number; Hmiltonian path; Hamiltonian cycle; linear array; ring; mesh; network 
Subjects:  A General Works > AI Indexes (General) 
Divisions:  Fakultas Ilmu Komputer dan Teknologi Informasi > Program Studi Sistem Informasi 
Depositing User:  Mr Reza Chandra 
Date Deposited:  25 Feb 2014 04:02 
Last Modified:  25 Feb 2014 04:02 
URI:  http://repository.gunadarma.ac.id/id/eprint/41 
Actions (login required)
View Item 