Exact wirelength of hypercubes on a grid

DOI10.1016/j.dam.2008.09.013zbMath1172.05330OpenAlexW1964247502MaRDI QIDQ1028121

Helda Mercy, Indra Rajasingh, Bharathi Rajan, Paul D. Manuel

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.09.013

zbMATH Keywords

embeddingdilationgridshypercubescongestionVLSI layoutwirelengthfixed interconnection parallel architecture

Mathematics Subject Classification ID

Paths and cycles (05C38) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items (42)

An asymptotic relation between the wirelength of an embedding and the Wiener index ⋮ Embedding complete multi-partite graphs into Cartesian product of paths and cycles ⋮ Wiener index via wirelength of an embedding ⋮ Wirelength of enhanced hypercubes into \(r\)-rooted complete binary trees ⋮ Embeddings of circulant networks ⋮ An algorithm for embedding Turán graphs into incomplete hypercubes with minimum wirelength ⋮ Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path ⋮ Wirelength of embedding complete multipartite graphs into certain graphs ⋮ Layout of embedding locally twisted cube into the extended theta mesh topology ⋮ Optimal embedding of hypercube into cylinder ⋮ Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees ⋮ A rigorous proof on circular wirelength for hypercubes ⋮ Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength ⋮ On linear layout of bicube and construction of optimal incomplete bicube ⋮ Wirelength of \(1\)-fault Hamiltonian graphs into wheels and fans ⋮ Minimum Linear Arrangement of Generalized Sierpinski Graphs ⋮ Embedding Wheel - like Networks ⋮ A linear time algorithm for embedding locally twisted cube into grid network to optimize the layout ⋮ Embedding of hypercubes into necklace, windmill and snake graphs ⋮ Minimum wirelength of hypercubes into \(n\)-dimensional grid networks ⋮ Optimal Embedding of Locally Twisted Cubes into Grids ⋮ On the optimal layout of balanced complete multipartite graphs into grids and tree related structures ⋮ Embedding of hypercubes into sibling trees ⋮ Bothway embedding of circulant network into grid ⋮ Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs ⋮ Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees ⋮ Linear wirelength of folded hypercubes ⋮ Wirelength of hypercubes into certain trees ⋮ Linear layout of locally twisted cubes ⋮ Unnamed Item ⋮ A linear time algorithm for embedding hypercube into cylinder and torus ⋮ Maximum incomplete recursive circulants in graph embeddings ⋮ Node set optimization problem for complete Josephus cubes ⋮ Embedding of the folded hypercubes into tori ⋮ Linear layout of directed grid graph ⋮ Embedding of recursive circulants into certain necklace graphs ⋮ Characterization of the congestion lemma on layout computation ⋮ Unnamed Item ⋮ Embedding algorithm of spined cube into grid structure and its wirelength computation ⋮ Optimal Wirelength of Balanced Complete Multipartite Graphs onto Cartesian Product of {Path, Cycle} and Trees ⋮ Square-root rule of two-dimensional bandwidth problem ⋮ Conjectures on wirelength of hypercube into cylinder and torus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• The cyclic cutwidth of trees
• Algorithms for drawing graphs: An annotated bibliography
• Embedding ladders and caterpillars into the hypercube
• On embedding complete graphs into hypercubes
• Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
• The congestion of \(n\)-cube layout on a rectangular grid
• Cutwidth of ther-dimensional Mesh ofd-ary Trees
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Embedding star networks into hypercubes
• Embedding of cycles and wheels into arbitrary trees
• Crossing Numbers and Cutwidths
• Degree constrained book embeddings
• Efficient embeddings of grids into grids
• Optimal embeddings of generalized ladders into hypercubes
• Embedding complete trees into the hypercube

This page was built for publication: Exact wirelength of hypercubes on a grid