A linear time algorithm for embedding Christmas trees into certain trees

DOI10.1142/S0129626415500085MaRDI QIDQ4598908zbMATH OpenFDO

Authors R. Sundara Rajan, Paul Manuel, Indra Rajasingh

Publication date 15 December 2017

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

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)

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

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)