Embeddings Of Linear Arrays, Rings And 2-D meshes On Extended lucas Cube Network

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


Download (354Kb) | Preview


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 Fibonacci-like cube, namely Extended Lucas Cube (ELC). We address the following network simulation problem : Given a linear array, a ring or a two-dimensional 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 View Item