The complexity of minimizing wire lengths in VLSI layouts

DOI10.1016/0020-0190(87)90173-6zbMath0653.68020MaRDI 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

zbMATH Keywords

NP-complete; VLSI layout; wire length

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

Related Items

Optimal grid representations, Complexity dichotomy on partial grid recognition, Weak sense of direction labelings and graph embeddings, Two models of two-dimensional bandwidth problems, Approximation algorithms for the bandwidth minimization problem for a large class of trees, A framework for solving VLSI graph layout problems, Lattice bandwidth of random graphs, The strength of weak proximity, Complexity results for three-dimensional orthogonal graph drawing, A minimization version of a directed subgraph homeomorphism problem, Embedding ternary trees in VLSI arrays, Unit-length embedding of binary trees on a square grid, Drawing orders using less ink, The logic engine and the realization problem for nearest neighbor graphs, The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Expansion of layouts of complete binary trees into grids, Three-dimensional orthogonal graph drawing algorithms, The realization problem for Euclidean minimum spanning trees is NP-hard, Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges, A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs, Tree Drawings on the Hexagonal Grid, Isometric Diamond Subgraphs

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