The complexity of minimizing wire lengths in VLSI layouts
From MaRDI portal
Publication:1107990
DOI10.1016/0020-0190(87)90173-6zbMath0653.68020OpenAlexW1981227591MaRDI QIDQ1107990
Sandeep N. Bhatt, Stavros S. Cosmandakis
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(87)90173-6
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (38)
Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges ⋮ On Embeddability of Unit Disk Graphs onto Straight Lines ⋮ The logic engine and the realization problem for nearest neighbor graphs ⋮ The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings ⋮ Embedding ternary trees in VLSI arrays ⋮ The strength of weak proximity ⋮ Unit-length embedding of binary trees on a square grid ⋮ The realization problem for Euclidean minimum spanning trees is NP-hard ⋮ A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid ⋮ Nearest neighbour graph realizability is NP-hard ⋮ On embeddability of unit disk graphs onto straight lines ⋮ Combinatorial properties and recognition of unit square visibility graphs ⋮ On complexity of multidistance graph recognition in \(\mathbb{R}^1\) ⋮ Unit-length rectangular drawings of graphs ⋮ On Local Structures of Cubicity 2 Graphs ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Weak sense of direction labelings and graph embeddings ⋮ Expansion of layouts of complete binary trees into grids ⋮ On Upward Drawings of Trees on a Given Grid ⋮ Two models of two-dimensional bandwidth problems ⋮ On the edge-length ratio of outerplanar graphs ⋮ A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs ⋮ Approximation algorithms for the bandwidth minimization problem for a large class of trees ⋮ Complexity results for three-dimensional orthogonal graph drawing ⋮ Optimal grid representations ⋮ Drawing orders using less ink ⋮ Complexity dichotomy on partial grid recognition ⋮ Tree Drawings on the Hexagonal Grid ⋮ Isometric Diamond Subgraphs ⋮ Unnamed Item ⋮ Efficient algorithms for network localization using cores of underlying graphs ⋮ A minimization version of a directed subgraph homeomorphism problem ⋮ Three-dimensional orthogonal graph drawing algorithms ⋮ A framework for solving VLSI graph layout problems ⋮ On the Edge-Length Ratio of 2-Trees ⋮ Self-adjusting grid networks to minimize expected path length ⋮ Self-adjusting Grid Networks to Minimize Expected Path Length ⋮ Lattice bandwidth of random graphs
Cites Work
- Unnamed Item
- A framework for solving VLSI graph layout problems
- The NP-completeness of the bandwidth minimization problem
- Efficient detection of determinacy races in cilk programs
- NP-completeness for minimizing maximum edge length in grid embeddings
- Encoding Data Structures in Trees
- Universality considerations in VLSI circuits
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Complexity Results for Bandwidth Minimization
- The complexity of satisfiability problems
- The NP-completeness column: An ongoing guide
This page was built for publication: The complexity of minimizing wire lengths in VLSI layouts
