Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength

DOI10.1016/j.dam.2011.07.003zbMath1239.05123OpenAlexW2025791275MaRDI QIDQ411854

J. Herrera, H. S. Yoon

Publication date: 30 April 2012

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

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

zbMATH Keywords

embeddinghypercubescongestionwirelengthedge isoperimetric problem

Mathematics Subject Classification ID

Hypergraphs (05C65) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (16)

Wirelength of embedding complete multipartite graphs into certain graphs ⋮ On excessive index of certain networks ⋮ Optimal embedding of hypercube into cylinder ⋮ Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees ⋮ Embedding Wheel - like Networks ⋮ Embedding of hypercubes into necklace, windmill and snake graphs ⋮ Embedding of hypercubes into sibling trees ⋮ Bothway embedding of circulant network into grid ⋮ Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees ⋮ 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 ⋮ Embedding of recursive circulants into certain necklace graphs ⋮ Conjectures on wirelength of hypercube into cylinder and torus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Embedding of tori and grids into twisted cubes
• Embedding meshes/tori in faulty crossed cubes
• A framework for solving VLSI graph layout problems
• Dense sets and embedding binary trees into hypercubes
• On embeddings of snarks in the torus
• Embedding meshes into locally twisted cubes
• Path embedding in star graphs
• Exact wirelength of hypercubes on a grid
• Embedding the incomplete hypercube in books
• The cyclic cutwidth of trees
• An edge-isoperimetric problem for powers of the Petersen graph
• The edge-isoperimetric problem for discrete tori
• Wirelength of hypercubes into certain trees
• 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
• Embedding meshes into crossed cubes
• Two-Processor Scheduling with Start-Times and Deadlines
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Embedding of cycles and wheels into arbitrary trees
• Crossing Numbers and Cutwidths
• Augmented cubes
• 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: Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength