New lower bound techniques for VLSI
From MaRDI portal
Publication:3950484
DOI10.1007/BF01744433zbMath0488.94048MaRDI QIDQ3950484
Publication date: 1984
Published in: Mathematical Systems Theory (Search for Journal in Brave)
parallel computation; crossing number; graph embedding; very large scale integration; separator; mesh of trees; bisection width; layout area; tree of meshes; wire length; Thompson grid model; area-efficient chip layouts; maximum edge length; N-node planar graph; wire area
68R10: Graph theory (including graph drawing) in computer science
94C15: Applications of graph theory to circuits and networks
Related Items
Crossing numbers of random graphs, Representing shared data on distributed-memory parallel computers, SIMULTANEOUS ARITHMETIC PROGRESSIONS ON ALGEBRAIC CURVES, A Bipartite Strengthening of the Crossing Lemma, Graph theory (algorithmic, algebraic, and metric problems), Complexities of layouts in three-dimensional VLSI circuits, Deterministic P-RAM simulation with constant redundancy, A framework for solving VLSI graph layout problems, Multilayer grid embeddings for VLSI, A lower bound on the area of permutation layouts, A bipartite strengthening of the crossing Lemma, On edges crossing few other edges in simple topological complete graphs, Extremal problems on triangle areas in two and three dimensions, Long edges in the layouts of shuffle-exchange and cube-connected cycles graphs, A compact layout for the three-dimensional tree of meshes, Representations of graphs and networks (coding, layouts and embeddings), Parallel restructuring and evaluation of expressions, Shallow grates, An asymptotically optimal layout for the shuffle-exchange graph, Which crossing number is it anyway?, Crossing number, pair-crossing number, and expansion, Feedback vertex sets in mesh-based networks, On the decay of crossing numbers, Crossing and Weighted Crossing Number of Near-Planar Graphs
Cites Work
- Unnamed Item
- Area-time optimal VLSI networks for multiplying matrices
- The VLSI Complexity of Sorting
- A model of computation for VLSI with related complexity results
- Universality considerations in VLSI circuits
- Applications of a Planar Separator Theorem
- Bounds to Complexities of Networks for Sorting and for Switching
- The crossing number of K5,n
