The complexity of minimizing wire lengths in VLSI layouts

Cites work

A framework for solving VLSI graph layout problems
Complexity Results for Bandwidth Minimization
Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
Efficient detection of determinacy races in cilk programs
Encoding Data Structures in Trees
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
NP-completeness for minimizing maximum edge length in grid embeddings
The complexity of satisfiability problems
The NP-completeness column: An ongoing guide
The NP-completeness of the bandwidth minimization problem
Universality considerations in VLSI circuits

Cited in

(47)

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
On complexity of multidistance graph recognition in \(\mathbb{R}^1\)
The realization problem for Euclidean minimum spanning trees is NP-hard
Self-adjusting grid networks to minimize expected path length
Self-adjusting grid networks to minimize expected path length
Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges
On local structures of cubicity 2 graphs
A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs
scientific article; zbMATH DE number 3891093 (Why is no real title available?)
Tree Drawings on the Hexagonal Grid
Isometric Diamond Subgraphs
Minimum-diameter cyclic arrangements in mapping data-flow graphs onto VLSI arrays
On upward drawings of trees on a given grid
Optimal grid representations
scientific article; zbMATH DE number 750011 (Why is no real title available?)
On the Edge-Length Ratio of 2-Trees
On Embeddability of Unit Disk Graphs onto Straight Lines
Nearest neighbour graph realizability is NP-hard
Combinatorial properties and recognition of unit square visibility graphs
Complexity dichotomy on partial grid recognition
On embeddability of unit disk graphs onto straight lines
Combinatorial properties and recognition of unit square visibility graphs
Unit-length rectangular drawings of graphs
Grid recognition: classical and parameterized computational perspectives
Weak sense of direction labelings and graph embeddings
Two models of two-dimensional bandwidth problems
Unit-length rectangular drawings of graphs
Approximation algorithms for the bandwidth minimization problem for a large class of trees
Recognition complexity of subgraphs of \({\mathbf{k}}\)-connected planar cubic graphs
On the complexity of embedding in graph products
Drawn tree decomposition: new approach for graph drawing problems
Efficient recognition of subgraphs of planar cubic bridgeless graphs
The time complexity of oriented chromatic number for acyclic oriented connected subcubic subgraphs of grids
Efficient algorithms for network localization using cores of underlying graphs
A framework for solving VLSI graph layout problems
Lattice bandwidth of random graphs
Optimal wire ordering and spacing in low power semiconductor design
The strength of weak proximity
Complexity results for three-dimensional orthogonal graph drawing

This page was built for publication: The complexity of minimizing wire lengths in VLSI layouts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107990)