Embedding complete multipartite graphs into certain trees

MaRDI QIDQ5133195zbMATH OpenFDO

Authors A. Arul Shantrinal, R. Sundara Rajan, A. Ramesh Babu, S. Anil, Mohammed Ali Ahmed

Publication date 12 November 2020

Full work available at URL https://arxiv.org/abs/1910.10643

zbMATH Keywords

binary treecomplete multipartite graphsembeddingsibling treewirelength

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph theory (including graph drawing) in computer science (68R10)

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 embed complete multipartite graphs into certain trees, such as $k$-rooted complete binary trees and $k$-rooted sibling trees.

Recommendations

• On the optimal layout of balanced complete multipartite graphs into grids and tree related structures
• Wirelength of embedding complete multipartite graphs into certain graphs
• Incomplete hypercubes: Embeddings of tree-related networks
• Embedding of hypercubes into banana trees
• Congestion-free, dilation-2 embedding of complete binary trees into star graphs

Cited in

(12)

• Bipartite embeddings of trees in the plane
• Wirelength of embedding complete multipartite graphs into certain graphs
• On the optimal layout of balanced complete multipartite graphs into grids and tree related structures
• Embeddings and other mappings of rooted trees into complete trees
• scientific article; zbMATH DE number 4147467 (Why is no real title available?)
• Self‐dual embeddings of complete multipartite graphs
• Optimal wirelength of balanced complete multipartite graphs onto Cartesian product of \{path, cycle\} and trees
• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• An algorithm for embedding Turán graphs into incomplete hypercubes with minimum wirelength
• Embedding hierarchical cubic networks into k-rooted complete binary trees for minimum wirelength
• Maximum subgraph and wirelength analysis of extended Sierpiński networks in parallel computing
• Cuts, trees and \(\ell_1\)-embeddings of graphs

This page was built for publication: Embedding complete multipartite graphs into certain trees

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