On the complexity of tree embedding problems

DOI10.1016/0020-0190(92)90108-8zbMath0768.68059OpenAlexW2063276292MaRDI 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

treeembeddingVLSIpolynomial time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) 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)

Related Items (1)

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

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