On the complexity of tree embedding problems

DOI10.1016/0020-0190(92)90108-8MaRDI QIDQ1209372zbMATH OpenOpenAlexFDO

Authors Shai Simonson, I. H. Sudborough

Publication date 16 May 1993

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

Full work available at URL https://doi.org/10.1016/0020-0190(92)90108-8

zbMATH Keywords

treeembeddingVLSIpolynomial time algorithms

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Cost Trade-offs in Graph Embeddings, with Applications
• On embedding graphs in trees
• Optimal embedding of complete binary trees into lines and grids
• Publication:4694714
• Publication:4540091

Cites work

• A polynomial algorithm for the min-cut linear arrangement of trees
• A variation on the min cut linear arrangement problem
• Alternation
• Complexity Results for Bandwidth Minimization
• Cost Trade-offs in Graph Embeddings, with Applications
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Encoding Data Structures in Trees
• Graphs That are Almost Binary Trees
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• On Embedding Rectangular Grids in Square Grids
• Routing with critical paths
• Three-Dimensional VLSI

Cited in

(21)

• Optimal arrangement of data in a tree directory
• scientific article; zbMATH DE number 1405694 (Why is no real title available?)
• The parallel complexity of tree embedding problems (extended abstract)
• The Parallel Complexity of Tree Embedding Problems
• On embedding graphs in trees
• Embedding Graphs with Bounded Treewidth into Their Optimal Hypercubes
• scientific article; zbMATH DE number 3945345 (Why is no real title available?)
• An optimal emulator and VLSI layout for complete binary trees
• On optimal embeddings and trees
• Embedding of \(K_r+K^c_s\) and \(K_r+P_s\) into arbitrary trees
• Minimum layout of circulant graphs into certain height balanced trees
• scientific article; zbMATH DE number 3866594 (Why is no real title available?)
• A linear time algorithm for embedding Christmas trees into certain trees
• Cost Trade-offs in Graph Embeddings, with Applications
• Towards optimal embedding of an arbitrary tree in a graceful tree
• Optimal one-page tree embeddings in linear time
• Salvage-Embeddings of Complete Trees
• scientific article; zbMATH DE number 125491 (Why is no real title available?)
• Embedding of cycles and wheels into arbitrary trees
• scientific article; zbMATH DE number 219230 (Why is no real title available?)
• Minimum average congestion of enhanced and augmented hypercubes into complete binary trees

This page was built for publication: On the complexity of tree embedding problems

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