On the complexity of tree embedding problems
DOI10.1016/0020-0190(92)90108-8zbMATH Open0768.68059OpenAlexW2063276292MaRDI QIDQ1209372FDOQ1209372
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
Recommendations
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)
Cites Work
- Alternation
- On Embedding Rectangular Grids in Square Grids
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Complexity Results for Bandwidth Minimization
- A polynomial algorithm for the min-cut linear arrangement of trees
- A variation on the min cut linear arrangement problem
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Encoding Data Structures in Trees
- Three-Dimensional VLSI
- Cost Trade-offs in Graph Embeddings, with Applications
- Routing with critical paths
- Graphs That are Almost Binary Trees
Cited In (21)
- Embedding Graphs with Bounded Treewidth into Their Optimal Hypercubes
- Title not available (Why is that?)
- An optimal emulator and VLSI layout for complete binary trees
- Cost Trade-offs in Graph Embeddings, with Applications
- Embedding of cycles and wheels into arbitrary trees
- A linear time algorithm for embedding Christmas trees into certain trees
- Optimal one-page tree embeddings in linear time
- Salvage-Embeddings of Complete Trees
- Title not available (Why is that?)
- Title not available (Why is that?)
- Towards optimal embedding of an arbitrary tree in a graceful tree
- Title not available (Why is that?)
- Minimum average congestion of enhanced and augmented hypercubes into complete binary trees
- Embedding of \(K_r+K^c_s\) and \(K_r+P_s\) into arbitrary trees
- On embedding graphs in trees
- Title not available (Why is that?)
- Minimum layout of circulant graphs into certain height balanced trees
- The parallel complexity of tree embedding problems (extended abstract)
- On optimal embeddings and trees
- Optimal arrangement of data in a tree directory
- The Parallel Complexity of Tree Embedding Problems
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)
