Embedding ladders and caterpillars into the hypercube

DOI10.1016/S0166-218X(97)00101-7zbMath0906.05019MaRDI QIDQ1392524

Gerd Wechsung, Burkhard Monien, Walter Unger, Sergei L. Bezrukov

Publication date: 14 February 1999

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

hypercubeembeddingcaterpillarsladders

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (23)

Spanning multi-paths in hypercubes ⋮ Wirelength of enhanced hypercubes into \(r\)-rooted complete binary trees ⋮ Dense sets and embedding binary trees into hypercubes ⋮ Layout of embedding locally twisted cube into the extended theta mesh topology ⋮ Embedding certain height-balanced trees and complete \(p^m\)-ary trees into hypercubes ⋮ Embedding ladders and caterpillars into the hypercube ⋮ Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees ⋮ Minimum average congestion of enhanced and augmented hypercubes into complete binary trees ⋮ 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 ⋮ Embedding a subclass of trees into hypercubes ⋮ Linear layout of locally twisted cubes ⋮ Unnamed Item ⋮ Maximum incomplete recursive circulants in graph embeddings ⋮ Optimal embeddings of odd ladders into a hypercube ⋮ Embedding of the folded hypercubes into tori ⋮ Exact wirelength of hypercubes on a grid ⋮ Optimal Wirelength of Balanced Complete Multipartite Graphs onto Cartesian Product of {Path, Cycle} and Trees ⋮ Compression and expansion in graphs using overlays ⋮ A note on the cubical dimension of new classes of binary trees ⋮ Embedding some hierarchical caterpillars into hypercube

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A determination of the number of caterpillars
• Embedding all binary trees in the hypercube
• Parallel concepts in graph theory
• Embedding ladders and caterpillars into the hypercube
• The number of caterpillars
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• On Hamiltonian circuits and spanning trees of hypercubes
• One-legged caterpillars span hypercubes
• Bandwidth Minimization: An approximation algorithm for caterpillars
• Efficient Embeddings of Trees in Hypercubes
• Spanning caterpillars of a hypercube

This page was built for publication: Embedding ladders and caterpillars into the hypercube