A linear time algorithm for embedding Christmas trees into certain trees

DOI10.1142/S0129626415500085zbMATH Open1376.68115MaRDI QIDQ4598908FDOQ4598908

Authors: R. Sundara Rajan, Paul Manuel, Indra Rajasingh 

Publication date: 15 December 2017

Published in: Parallel Processing Letters (Search for Journal in Brave)

Recommendations

• On the complexity of tree embedding problems
• Optimal one-page tree embeddings in linear time
• Lattice embeddings of trees
• Minimum layout of circulant graphs into certain height balanced trees
• Embedding of cycles and wheels into arbitrary trees

zbMATH Keywords

embeddingdilationwirelengthChristmas trees

Mathematics Subject Classification ID

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

Cited In (5)

• Maximum subgraph problem for 3-regular Knödel graphs and its wirelength
• Minimum linear arrangement of the Cartesian product of optimal order graph and path
• Minimum layout of circulant graphs into certain height balanced trees
• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• Embedding of hypercube into fractal cubic network

This page was built for publication: A linear time algorithm for embedding Christmas trees into certain trees

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