On the complexity of tree embedding problems

DOI10.1016/0020-0190(92)90108-8zbMath0768.68059MaRDI QIDQ1209372

Shai Simonson, Ivan Hal 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

tree; embedding; VLSI; polynomial time algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

94C15: Applications of graph theory to circuits and networks

Related Items

Minimum average congestion of enhanced and augmented hypercubes into complete binary trees

Cites Work

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