Embedding Wheel - like Networks
From MaRDI portal
Abstract: One of the important features of an interconnection network is its ability to efficiently simulate programs or parallel algorithms written for other architectures. Such a simulation problem can be mathematically formulated as a graph embedding problem. In this paper we compute the lower bound for dilation and congestion of embedding onto wheel-like networks. Further, we compute the exact dilation of embedding wheel-like networks into hypertrees, proving that the lower bound obtained is sharp. Again, we compute the exact congestion of embedding windmill graphs into circulant graphs, proving that the lower bound obtained is sharp. Further, we compute the exact wirelength of embedding wheels and fans into 1,2-fault hamiltonian graphs. Using this we estimate the exact wirelength of embedding wheels and fans into circulant graphs, generalized Petersen graphs, augmented cubes, crossed cubes, M"{o}bius cubes, twisted cubes, twisted -cubes, locally twisted cubes, generalized twisted cubes, odd-dimensional cube connected cycle, hierarchical cubic networks, alternating group graphs, arrangement graphs, 3-regular planer hamiltonian graphs, star graphs, generalised matching networks, fully connected cubic networks, tori and 1-fault traceable graphs.
Recommendations
- Exact wirelength of embedding circulant networks into necklace and windmill graphs.
- Exact wirelength of circulant networks into cycle-of-ladders.
- Embedding of cycles and wheels into arbitrary trees
- Embedding circulant networks into butterfly and benes networks
- Embedding of hypercubes into necklace, windmill and snake graphs
Cites work
- A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
- Arrangement graphs: A class of generalized star graphs
- Asymptotics of the average number of nondominant options of binary relations
- Augmented cubes
- Cycles embedding in folded hypercubes with conditionally faulty vertices
- 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 cycles and wheels into arbitrary trees
- Embedding of cycles in twisted cubes with edge-pancyclic
- 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 hypercubes on a grid
- Fault Hamiltonicity and fault Hamiltonian connectivity of the (n,k)-star graphs
- Fault Hamiltonicity and fault Hamiltonian-connectivity of generalised matching networks
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1751602 (Why is no real title available?)
- Hyper-Hamiltonian generalized Petersen graphs
- Locally twisted cubes are 4-pancyclic.
- Minimum wirelength of hypercubes into \(n\)-dimensional grid networks
- On embedding rectangular grids in hypercubes
- On some super fault-tolerant Hamiltonian graphs
- Optimal 1-Hamiltonian graphs
- Optimal embeddings of generalized ladders into hypercubes
- Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements
- Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs
- Paths and cycles embedding on faulty enhanced hypercube networks
- Survey on path and cycle embedding in some networks
- The congestion of \(n\)-cube layout on a rectangular grid
- The cyclic cutwidth of trees
- The Mobius cubes
- Two construction schemes for cubic Hamiltonian 1-node-Hamiltonian graphs
- Wirelength of \(1\)-fault Hamiltonian graphs into wheels and fans
- Wirelength of embedding complete multipartite graphs into certain graphs
- Wirelength of hypercubes into certain trees
This page was built for publication: Embedding Wheel - like Networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187747)
