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
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
