Embedding of hypercubes into necklace, windmill and snake graphs

Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. In this paper, we determine the exact wirelength of embedding hypercubes into necklace, windmill and snake graphs. ► Embedding and Exact wirelength problems are NP-complete....

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2012-06, Vol.112 (12), p.509-515
Main Authors: Rajasingh, Indra, Rajan, Bharati, Rajan, R. Sundara
Format: Article
Language:English
Subjects:
Computer architecture
Congestion
Data processing
Edge isoperimetric problem
Embedding
Graph theory
Graphs
Hypercubes
Interconnection
Interconnection networks
Network topologies
Networks
Parallel computers
Snakes
Studies
Windmills
Wirelength
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. In this paper, we determine the exact wirelength of embedding hypercubes into necklace, windmill and snake graphs. ► Embedding and Exact wirelength problems are NP-complete. ► We compute the exact wirelength of hypercube into certain graphs. ► We found the maximum subgraph for hypercubes. ► We define certain host graphs and it is a superior network for research.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2012.03.006