A linear time algorithm for embedding hypercube into cylinder and torus

DOI10.1016/J.TCS.2014.05.007MaRDI QIDQ2015139zbMATH OpenOpenAlexFDO

Authors R. Sundara Rajan, Indra Rajasingh, N. Parthiban, T. M. Rajalaxmi

Publication date 23 June 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.05.007

zbMATH Keywords

cylinderembeddinghypercubetoruswirelength

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Conjectures on wirelength of hypercube into cylinder and torus
• Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
• Linear wirelength of folded hypercubes
• Embedding of hypercubes into generalized books.
• Exact wirelength of hypercubes on a grid

Cites work

• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• An edge-isoperimetric problem for powers of the Petersen graph
• Efficient embeddings of grids into grids
• Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
• Embedding meshes into crossed cubes
• Embedding meshes into locally twisted cubes
• Embedding meshes/tori in faulty crossed cubes
• Embedding of hypercubes into necklace, windmill and snake graphs
• Embedding of meshes in Möbius cubes
• Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs
• Embedding of tori and grids into twisted cubes
• Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
• Exact wirelength of embedding circulant networks into necklace and windmill graphs.
• Exact wirelength of hypercubes on a grid
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 4147467 (Why is no real title available?)
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3725713 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2010366 (Why is no real title available?)
• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• Minimum wirelength of hypercubes into \(n\)-dimensional grid networks
• On embedding rectangular grids in hypercubes
• Optimal embeddings of generalized ladders into hypercubes
• The congestion of \(n\)-cube layout on a rectangular grid
• The cyclic cutwidth of trees

Cited in

(8)

• Conjectures on wirelength of hypercube into cylinder and torus
• Optimal embedding of hypercube into cylinder
• A rigorous proof on circular wirelength for hypercubes
• Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
• An Efficient Algorithm for Embedding Two-Dimensional Tori into Balanced Hypercubes
• Embedding hypercubes into torus and Cartesian product of paths and/or cycles for minimizing wirelength
• Linear wirelength of folded hypercubes
• An upper bound for edge congestion and the exact wirelength of embedding onto BC graphs

This page was built for publication: A linear time algorithm for embedding hypercube into cylinder and torus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2015139)